## DESIGN AND ANALYSIS OF ALGORITHM

Find out some examples based on Time Complexity
23 October, 2016

Find out some Time Complexity :-

•    main()

{
int i;
}
Solution:       Statement = 1
Execution = 1
Complexity = O(1)
Exp: There is one statement which is going to be execute every time. int i is the statement so time complexity is 1.

main()

{
int i, n, x;
for(i=1; i<=n: i++)
{
x=x+1;
}
}
Solution:               Statement = 2
Execution = n+1
Complexity = O(n)
Exp:

There is two statements int i,n,x and x=x+1.
X=x+1 will execute n times so the equation is n=1.
Lower order terms and constant will discard
n+1 is the complexity and 1 is constant and we can remove it so our complexity is O(n) which is going to be execute every time.

main()

{
int i,n;
i=n;
while(i≥1)
{
i=i/2
}
}

Solution:          Statement = 3
Execution = logn
Complexity = O(logn)

Let n=2 so  i =2 ---1st time execution
because next time    i=1 so it will exit from the loop.
Now, let n=4 so i=4 -----1st execution
i=2 ----- 2nd execution
i=1 exit.

Now n=8 i=8 ----1st execution
I=4 --- 2nd execution
I=2 --- 3rd execution
i=1 exit.
So 2=>1 execution
4=>2 execution
8=> 3 execution

It will take logn complexity when input is n. main()

{
int  i, j, k;
i= i+1;
j=j+1;
k=k+1;
}
Solution:         Statement = 4
Execution =4
Complexity = o(1)
Exp:

There are four statement which is going to be execute every time so time complexity is 1. Constant does not matter.    It counts only one. 