time complexity exercise (pseudo code)

Just started Data Structure. Got stuck on this one:

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.

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.