CODEWITHSUNDEEP
time-complexitybig-o
sheldonzy
sheldonzy

Reputation: 5941

time complexity exercise (pseudo code)

Just started Data Structure. Got stuck on this one:

enter image description here

I am having trouble with the inner while and for loops, Because it changes if the N number is odd or even.

My best case will be - the inner for loop runs logn (base 2) times, And the while loop - logn times (base 2)

Would love some help.

Upvotes: 1

Views: 1066

Answers (2)

Mokhtar Mammeri
Mokhtar Mammeri

Reputation: 1

n^2*log(n) because the for loop it n and while is log(n) becuse counter *= 2 and the nested for in while loop we take the woest case is n finaly we hava n^2log(n)

Upvotes: 0

John Coleman
John Coleman

Reputation: 51998

Concentrate on how many times do_something() is called.

The outer for loop clearly runs n times, and the while loop inside it is independent of the variable i. Thus do_something() is called n times the total number of times it is called in the while loop.

In the first pass through the while loop, do_something() is called once. The second time, it is called twice, the third time it is called, 4 times, etc.

The total number of times it is called is thus

1 + 2 + 4 + 8 + ... + 2^(k-1)

where k is maximal such that 2^(k-1) <= n.

There is a standard formula for the above sum. Use it then solve for k in terms of n and multiply the result by the n from the outer loop, and you are done.

Upvotes: 1

Related Questions