CabDude CabDude - 1 year ago 139
Java Question

Time Complexity: While loop with nested for Loop[java]

So I just started learning time complexity and I have somewhat of an "okayish" grasp on it however I'm a little confused on how to go about this code segment.
I have read other posts but I just have a hard time grasping things unless someone butchers what I have to say. Kind of like a slap in the face.

public int example(int[] array) {

int result = 15;
int i = array.length;

while(i > 1)
for(int x = 0; x < array.length;x++)
result+= 1;
i = i/2;
return result;

Okay so I'm only counting arithmetic operations.
From what I believe, correct me if I'm wrong(probably am),

x++ happens n times.

result+= 1 happens n times.

result +=3 * array[x] happens 2n times

All for a total of 4n times

and i = i/2 happens logn times

So would the right equation be 4nlogn??

Answer Source

You are on the right track with 4n*log(n). However, note that for big O time complexity, constants are removed, so this would be O(n*log(n)).

Constants are removed because of the big O definition: f(x) is O(g(x)) if f(z) <= c*g(z) for all z > some number. The key here is the c which can be any constant. Even if your f(x) is 100x you could still have c=200 and g(x) would still be greater.

As a side note, since we can factor out constants, you don't have to count EVERY operation when calculating big O time complexity. You need only look at the loops. One happens n times, the other log(n) times. So it is O(n*log(n)). The code could perform 1000 operations inside each loop, or it could perform 2. Because constants are factored out of our big O equation, that number doesn't matter. Only the number and nature of the loops does.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download