CODEWITHSUNDEEP
mathbig-oasymptotic-complexity
StudentsTea
StudentsTea

Reputation: 349

Asymptotic analysis of a recurrence relation

I have a recurrence relation that models the runtime of an unknown algorithm, and I need to find either the lower bound of that algorithm's run time, or both the upper and lower bounds.

img

Pardon the rough formating; the Latex-to-image parser I used numbers equations strangely: the number for each equation is below and to the left of the markup to which the number refers.

Equations (1) and (2) are the parts of the recurrence relation.

To get from equation (2) to (3), write out a few iterations of the recurrence and observe the pattern that forms--then generalize it using the new variable k.

Note that that recurrence stops when equation (4) is true.

Substitute equation (4) into equation (3) to get equation (5). Also, use the logarithm change-of-base formula to get all logs in terms of base two.

From equation (5) to equation (6) I attempt to make some observation about equation (5) in terms of Big-oh analysis. But frankly this last step is just a guess on my part.

Supposing equation (5) is true, how would I express the theta, omega, or oh of equation (5), and--most importantly--how would one prove it?

My thought was--we're interested in knowing the behavior of equation (5) as n becomes very, very large. But the limit of equation (5) as n approaches infinity involves the log of a negative number, which--is a dead end, and probably wrong.

Any help is appreciated.

Upvotes: 0

Views: 394

Answers (1)

Lutz Lehmann
Lutz Lehmann

Reputation: 25992

The transformation from exponential to logarithm is wrong. There certainly exists some k such that

(10/9)^k <= n <= (10/9)^(k+1).

Applying dyadic logarithms 

k*log2(10/9) <= log2(n) <= (k+1)*log2(10/9)

which can be transformed to boundaries for k as in

log2(n)/log2(10/9) - 1 <= k <= log2(n)/log2(10/9)

which then results in

T(n) around T(1)+c*log2(n)/log2(10/9)

which is still asymptotically bound above and below by multiples of log2(n), but the corrected formula is "slightly" different.

Upvotes: 1

Related Questions