CODEWITHSUNDEEP
timecomplexity-theory
Jai Sharma
Jai Sharma

Reputation: 733

Algorithm time complexity analysis

I haven't got sufficient knowledge of time complexity, so my question is:

Is there any direct formula to calculate time complexity of an algorithm, example- I have read somewhere that big O of this code is n*log2(n), so can you tell me how they got this expression?

for(i=1;i<=n;i=i*2)

for this loop I am unable to calculate the big O. This loops will make 7 iterations for a value of n=100. How does that help arrive to the given formula?

Upvotes: 2

Views: 246

Answers (1)

Martin Dinov
Martin Dinov

Reputation: 8825

By itself, this loop will iterate through ceil(log(n)) times. That's log(n) with log base of 2. This is because after ceiling(log(n)) multiplications, i will have reached or passed n, for any n. A quick example:

For n=100:

Iteration:      i:
    1           1
    2           2
    3           4
    4           8
    5           16
    6           32
    7           64
    8           128

So i will be checked on the 8th iteration and you don't go into the loop, as it's not <= 100. It will be nlog2(n) as you suggest if there's another inner loop that fully loops through n times. Then the two times for the two loops get multiplied to get the total time.

Upvotes: 3

Related Questions