CODEWITHSUNDEEP
javabig-ocomplexity-theory
gravatasufoca
gravatasufoca

Reputation: 39

Complexity of algorithm in Big O notation

Consider the following code snippet:

for(int index = 1;index < N;index*=2){
    int counter = 0;
    while(counter < N){
       counter++;
    }
}

Determine its best - and worst - case runtime in the Big Theta notation as a function of N. Options:

a) Best case: O(log(N)) - Worst case: O(N²)

b) Best case: O(N . log(N)) - Worst case: O(N . log(N))

c) Best case: O(N . log(N)) - Worst case: O(N²)

d) Best case: O(N) - Worst case: O(N)

I saw this question in a Java assessment and I really don't know the right answer. I answered the option D, but I don't know if it is right. Could you help me with that?

Upvotes: 0

Views: 1409

Answers (3)

Balastrong
Balastrong

Reputation: 4464

The inner loop runs N times, so each cycle of the outer loop is O(N). The outer loop has its index increasing exponentially, then we can say it needs log(N) cycles.

Put them together and you'll have N log(N) in both cases as there isn't any "best" or "worse" condition, there's no way to exit that loop other than doing them all.

Upvotes: 2

ControlAltDel
ControlAltDel

Reputation: 35011

I believe the answer is N log N for both best and worst case

To start with, there is no short-circuiting. Which means best case must be the same as worst case

Second, The outer loop is going to run log(N) times, as index is doubled in every loop

Third, the inner loop accumulates from 0 to N - 1 stepping by one each time. So that's N operations

Thus N log N for both best and worst

Upvotes: 2

amit
amit

Reputation: 178441

This is O(NlogN) both best and worst case.

The inner loop repeats itself everytime it starts exactly the same number of times, which is N times.

The outer loop repeats itself logN times.

So, if you combine these, the total number of times counter is increased is:

T(n) = N + N + ... + N = N*logN

Which gives you total of O(NlogN) time.

Upvotes: 3

Related Questions