1,727 views
1 votes
1 votes
Which of the following is true about time complexity for generating $\color{blue} {n^{th}}$ Fibonacci number ?

a)$O(n)$

b)$O(Logn)$

c)$O(2^n)$

d)$\Omega(n)$

1 Answer

Best answer
2 votes
2 votes

Whenever there is some complexity based question of a problem and not a program snippet , what the questioner is looking that whether we know about the optimal solution to that problem or not . Hence answer must always be in light of worst case of best algorithm(optimal algorithm)..

For the given problem of Fibonacci number generation , we can do that in O(logn) time optimally using Fibonacci matrix .. It is a  2 * 2 matrix with  a11 = a12 = a21 = 1 and a22 = 0.

So after exponentiation of this matrix 'n' times we get  a11 = Fn+1  , a12 = a21 = Fn  ,   a22 = Fn-1   where Fis nth Fibonacci number..

Secondly the matrix of 1's and 0 as mentioned earlier can be raised to the power 'n' using divide and conquer exponentiation technique which works in O(logn) time . 

Hence Fn can be achieved in O(logn) time to be more accurate and optimal..

Hence keeping this in mind , the complexity of given problem   =  O(logn) ..

D) option is straightaway false because it says that time complexity cannot be less than 'n' in any case which is not the case here..And other options do not indicate optimal algorithm..

Hence B) should be the correct option here.

Suggested reading http://www.geeksforgeeks.org/program-for-nth-fibonacci-number/

selected by

Related questions

0 votes
0 votes
2 answers
1
3 votes
3 votes
1 answer
2
sumit_kumar asked Jun 25, 2017
3,126 views
what is time comlexity procedure for following recursive equation by substitution method:T(n)= T(n-1)+T(n-2) , if n>=2 =1 , if n=1; =0 , if n=0.
0 votes
0 votes
0 answers
3
Anuanu asked May 31, 2016
251 views