CODEWITHSUNDEEP
time-complexity
NANDAKUMAR THANGAVELU
NANDAKUMAR THANGAVELU

Reputation: 661

Computing Time Complexity in code

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.

Upvotes: 0

Views: 45

Answers (1)

huix
huix

Reputation: 124

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

Upvotes: 1

Related Questions