In particular, I'm interested in finding the Theta complexity. I can see the algorithm is bounded by log(n) but I'm not sure how to proceed considering the problem size decreases exponentially.
i = n
j = 2
while (i >= 1)
i = i/j
j = 2j
-
1You can just compute an explicit formula from the recurrence relation $T(n) = 1 + T(n/2)$ (which this program satisfies) and the master theorem. The theta complexity is exactly $log(N)$, since base case is $T(1) = 0$Akshat Mahajan– Akshat Mahajan2018-02-06 07:54:08 +00:00Commented Feb 6, 2018 at 7:54
-
4Since the factor 'b' in T(n) = aT(n/b) + f(n) isn't a constant for this algorithm, isn't it incorrect to use the master theorem? That is, b increases by a factor of 2 for each successive problem.Francisco Pizarro– Francisco Pizarro2018-02-06 08:03:36 +00:00Commented Feb 6, 2018 at 8:03
-
My mistake, you are correctAkshat Mahajan– Akshat Mahajan2018-02-06 08:04:27 +00:00Commented Feb 6, 2018 at 8:04
Add a comment
|
2 Answers
The simplest way to answer your question is to look at the algorithm through the eyes of the logarithm (in my case the binary logarithm):
log i_0 = log n
log j_0 = 1
k = 0
while (log i_k >= 0) # as log increases monotonically
log i_{k+1} = log i_k - log j_k
log j_{k+1} = (log j_k) + 1
k++
This way we see that log i decreases by log j = k + 1 during every step.
Now when will we exit the loop?
This happens for
The maximum number of steps is thus the smallest integer k such that
holds.
Asymptotically, this is equivalent to 
, so your algorithm is in 
1 Comment
Francisco Pizarro
Thank you for this neat method. It took a few reads to sink in but it makes sense now.
Let us denote i(k) and j(k) the value of i and j at iteration k (so assume that i(1)=n and j(1)=2 ). We can easily prove by induction that j(k)=2^k and that
Knowing the above formula on i(k), you can compute an upper bound on the value of k that is needed in order to have i(k) <= 1 and you will obtain that the complexity is 
