Lower Bound of Fibonacci Big Omega Time Complexity

Lower Bound of Fibonacci Big Omega Time Complexity:


 Code for Recursive Fibonacci Algorithm:

int fib(int n){
	if (n < 2)
		return n;
	else
		return fib(n - 1) + fib(n - 2);
}

Time Complexity Lower Bound ( Big Omega ):

Detailed explanation for calculating the upper and lower bound can be found here.

T(n) =  T(n-1) + T(n-2) + c
	 =  T(n-2) + T(n-3) + c + T(n-2) + c
	 =  2T(n-2) + T(n-3) + 2c
	 >= 2T(n-2) + 2c
	 =  2T(n-3) + T(n-4) + c) + 2c
	 =  2T(n-3) + 2T(n-4) + 2c + 2c
	 =  2T(n-3) + 2T(n-4) + 4c
	 =  2T(n-4) + 2T(n-5) + 2c + 2T(n-4) + 4c
	 =  4T(n-4) + 2T(n-5) + 6c
	 >= 4T(n-4) + 6c
	 =  4T(n-5) + 4T(n-6) + 10c
	 =  4T(n-6) + 4T(n-7) + 4c + 4T(n-6) + 10c
	 =  8T(n-6) + 4T(n-7) + 14c
	 >= 8T(n-6) + 14c
	 =  .......................
	 =  .......................
	 =  2^k T(n - 2k) + (2^(k+1)-2)c



for, k steps, n - 2k = 0 or, 1 the recursion stops
			  => n = 2k
			  => k = n / 2



	so, from the recurrence relation
	= 2^(n/2) * T(0) + (2^((n/2) +1) -2) * c
	= 2^(n/2) * c + (2^((n/2) +1) -2) * c
	= Ω(2^(n/2))

So, the lower bound of for this recursive Fibonacci algorithm implementation is Big Omega of 2n / 2.

Lower Bound:  Ω ( 2n / 2  )

Advertisements

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s