Proving Fibonacci recursive algorithm time complexity

Question

I am trying to understand a proof by induction in my algorithms text book. Here's the author is proving using induction that the T(n) will always be greater than 2^(n/2) (This is for calculating the nth fibonacci number using the recursive algorithm): enter image description here

What I don't understand is the very last step, where he is manipulating the equation. How does he go from:

> 2^(n-1)/2 + 2^(n-2)/2 +1

to

> 2^(n-2)/2 + 2^(n-2)/2 +1

He just randomly changes 2^(n-1)/2 to 2^(n-2)/2. Is this a mistake?

Thanks.

Karoly Horvath · Accepted Answer · 2011-09-30 08:19:33Z

5

It's deliberate, if you look closely it's an inequation and he uses it do finish the induction step.

Note the typo, it should say "We must show that T(n) > 2^(n/2)" and not <.

answered Sep 30, 2011 at 8:19

Karoly Horvath

96.7k11 gold badges123 silver badges181 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

user155407 · Accepted Answer · 2011-09-30 08:58:54Z

3

I believe that particular step runs off the assumption that:

T(n-1) > T(n-2)

Therefore, we can form an algebraic inequality:

T(n-1) + T(n-2) + 1 > T(n-2) + T(n-2) + 1

We can lop off the + 1 from the right side (because the inequality will still hold true for anything subtracted away on the LESSER side):

T(n-1) + T(n-2) + 1 > T(n-2) + T(n-2)

From this, substitute our T(m) = 2^(m/2) (for anything less than n and > 2, which n-1 and n-2 both qualify):

2^(n-1)/2 + 2^(n-2)/2 + 1 > 2^(n-2)/2 + 2^(n-2)/2

That gets you that particular step. It's done this way deliberately as the poster above me stated, to get to 2^(n/2).

answered Sep 30, 2011 at 8:58

user155407

Collectives™ on Stack Overflow

Proving Fibonacci recursive algorithm time complexity

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related