Time complexity measurement

Time complexity measurement of an Algorithm

            Once we think about an algorithm that how much it good or bad. Two things come automatically with it –

·         Time Complexity

·         Space Complexity

In today we don’t think so much about Space Complexity but once we will try to be a better coder or if we work on some real product or if we want give a better performance of the application then its very much essential to know about Time complexity. As per name suggest its means how much time required for an algorithm, but the processing speed differ from one system to another system. So basically we count the no of steps of an algorithm and measure corresponding big ‘O’.

Steps in an algorithm:

Statement	Step Count	Comments
A+B	2	Addition and Assignment operation.
Return (B+C)	2	Addition and Return operation.
A= Array[1]	2	Assignment and array reference operation
I<10 || j>10	3(worst case)	< operation, || operation, > operation
	1(best case)	If i<10 is true then it will ignore the rest of the part(look difference between | and ||)
A = function(n)	2	Assignment and function call
For(i=0;i<n;i=i++)	3n+2	Initialization	1	I=0
		Comparison	N+1	I<n
		increment	n	I++
		assignment	n	I=i++
		Total	3n+2

Now go through an example to count the no of steps

Factorial(n):        If(n==1)             Return 1;        Else             Return n*(factorial(n-1))	N times will be compare 1 time for return 4*(n-1), Here (n-1) times for subtraction. (n-1) times for method call (n-1) times for multiplication (n-1) times for return statement
Total Step Count	N+1+4*(n-1) = 5n-3

                       

5n-3 is a linear equation and as per big O notation it will be O(n)