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)

N^th 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 n^th fibonacci number

Simple iterative algorithm to calculate N^th Fibonacci number is as follows

Algorithm:

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

T_n will hold the value for n^{th</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 n^th 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 r^th fibonacci number vs number of bits needed to represent it.

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

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