Question 1. (time complexiity quiz)

#1

in the Answer pdf :
Answer is b) O(N)
Explanation: For a input integer n, the innermost statement of fun() is executed following
times.
n + n/2 + n/4 + … 1
So time complexity T(n) can be written as
T(n) = O(n + n/2 + n/4 + … 1) = O(n)

My Doubt :
you have corrrectly stated T(n) = O(n +n/2…) right?
how is that equal to n???
(as per your bin, search explanation) shouldnt :

n + n/2 +n/4 + n/8 …n/(2^k) where k is number of steps?

and since,

n/(2^k) = 1
n = 2^k
k = log(n)???

so how did you equate

n + n/2 +n/4 + n/8 …….n/(2^k) = O(n) ???

Please elucidate…

Thank you !

Doubt regarding first question of the quiz
#2

@ilovetocode

We know that it will take logn steps for n to finally reduce to 1.
Thus the problem can be viewed as:
1 + 2 + 2^2 + … 2^k, where k = logn (base2)

Using sum of a geometric progression :
sum = 1*(2^((logn) + 1) - 1)/(2 - 1)
which is 2^((logn) + 1) - 1

logn + 1 = logn + log2 = log(2n)
2^log(2n) = 2*n

Thus sum = 2*n - 1
The time complexity is thus O(n).

I hope my answer was able to answer your query. Please mark the doubt as resolved if my solution is able to answer your query.

#3

Thanks Kshitij! got it! :slight_smile:
you should put that in the pdf tho.

#4

@ilovetocode
Will forward the suggestion