1
\$\begingroup\$

As per the instructions on this Tape Equlibrium-Codility

I've written the code

import java.util.Arrays;
public class TapeEqulibrium {
  int main(int[] array) {
    int minimumDiff = 100000;
    for (int i = 1; i < array.length; i++) {
        int differnce = Math.abs(Arrays.stream(array, 0, i).sum() - Arrays.stream(array, i, array.length).sum());
        minimumDiff = differnce < minimumDiff ? differnce : minimumDiff;
    }
    return minimumDiff;
   }
}

On submission, I have got correct answers for all test cases. But It says that the time complexity is O(n*n)and taking more than 6.00 seconds. while writing I thought that it falls under time complexity of O(n) or something (as I don't know much about that). So I need to know how to calculate the time complexity of this code.

\$\endgroup\$
  • \$\begingroup\$ Hey, welcome to Code Review! Here we review working code to make it better (faster, leaner, more secure/readable/maintainable). While a reviewer commenting on the time complexity of your code is likely (since you seem to exceed some time-limit, in which case you also might consider adding the tag time-limit-exceeded), note that you may receive different answers as well (all questions here are by definition open-ended). Have a look at our help center for more information. \$\endgroup\$ – Graipher Sep 7 '18 at 7:42
2
\$\begingroup\$

You inner loop contains:

int differnce = Math.abs(Arrays.stream(array, 0, i).sum() - Arrays.stream(array, i, array.length).sum());

That does (i-0) operations for first sum and (array.length-i) for second, for a total of array.length-i+i-0=array.length. As the size of input is n=array.length that really gives O(n*n). Replacing for-loops with Streams doesn't improve complexity, only hides it a bit.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.