Time Complexity and Nth Fibonacci computation time complexity

2 minute read


Time Complexity

In computer science time complexity of an algorithm is a estimation on time taken for the algorithm on a given input in terms of the size of the input. By size of Input we mean number of bits required to express the input

Well it sounded too complex, lets take an example and see,

Say we have a algorithm Max-Element, which essentially scans a given array once and finds the maximum element.

Input to this algorithm is a array (say of size n, which means it contains n integers). Input size (number of bits required to store input) = n*(size of each integer) = n*64 (assuming each integer is 8 byte long)

our algorithm, Max-Element scans the entire array, so it scans n*64 bits

Time Complexity = O(64*n) = O(n)

Nth Fibonacci number calculation

Our infamous Fibonacci sequence 1,1,2,3,5,8,13,………

when expressed as a equation, we have

Fib(n) = Fib(n-1) + Fib(n-2)

where Fib(n) represents nth fibonacci number

Simple iterative algorithm to calculate Nth Fibonacci number is as follows


1) Initialize Tn-1=1, Tn-2=1, Tn, counter=1
2) if counter == n, break
3) Tn = Tn-1 + Tn-2
4) counter += 1
5) GoTo 2

Tn will hold the value for nth</sub> fibonacci number

In the above algorithm, we are simply keeping track of (n-1)th and (n-2)th fibonacci numbers and adding them to get the nth fibonacci number

What is the time complexity to add tow numbers? If you guessed it a constant time then you are wrong, since I never mentioned that the two integers will fit into any of the existing primitive types like Integer, Long etc, which occupy either 32 or 64 (depending on the compiler architecture).

In general it takes O(b) time to add two numbers which can be represented using b bits. so in the above pseudo-code, we are adding two numbers (c=a+b), a, b are nothing but (r-1)th and (r-2)th fibonacci numbers, so it takes O(log(Fib(r))) time to add these. Bellow is the estimation of rth fibonacci number vs number of bits needed to represent it.

rno. of bits

so the 50th fibonacci number no longer fits in a 64 bit integer. A better estimation of the number of bits required to store rth fibonacci number is r itself. (can see in the above table)

Thus our time complexity to compute the nth fibonacci number = number of iterations * time complexity for each iteration =O(n) * O(n)=O(n2)