Computing Time Complexity in code

Question

I had a doubt in computing the time complexity in the following snippet.

Case 1:- for (i = n; i>=1 ; i=i/2) printf("%d", i);

Case 2:- for (i = 1; i < n; i=i*2) printf("%d", i)

Can I tell, the above codes, will take O(N/2) or O(log N) time complexity to run against the input?

Thanks in advance.

When you run it for various values of n, how many lines do you get? Does the number of lines seem to be proportional to log n? — Useless
– Useless, Commented Apr 4, 2016 at 12:50

huix · Accepted Answer · 2016-04-04 12:55:16Z

1

It takes O(log2(n)),just think about this.i=1,then print result is 1,then 2,4,8,16 until 2^x>n,then do math in it,x>log2(n),so the time complexity is O(log2(n))

answered Apr 4, 2016 at 12:55

huix

1345 bronze badges

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

Collectives™ on Stack Overflow

Computing Time Complexity in code

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