Algorithm time complexity analysis

Question

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?

example of code that is O(n^2logn)????? or else how are we to explain.... — SeekingAlpha
– SeekingAlpha, Commented Jan 30, 2014 at 6:45
for(i=0;i<=n;i=i*2)-for this loop i am unable to calculate the big O. — Jai Sharma
– Jai Sharma, Commented Jan 30, 2014 at 7:57
Oh sorry i made a mistake , actually its for(i=1;i<=n;i=i*2) — Jai Sharma
– Jai Sharma, Commented Jan 30, 2014 at 8:08
Isn't it log2(n)?. Because binary search complexity is the same, and index every time divided by 2. And in this case multiplied by 2. — Ashot Karakhanyan
– Ashot Karakhanyan, Commented Jan 30, 2014 at 8:30

Martin Dinov · Accepted Answer · 2014-02-12 12:08:14Z

3

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.

answered Feb 12, 2014 at 12:08

Martin Dinov

8,8553 gold badges31 silver badges42 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Algorithm time complexity analysis

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related