CabDude - 9 months ago 61

Java Question

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;

result+=2*array[x];

}

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),

All for a total of

and

So would the right equation be

Answer

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.

Source (Stackoverflow)