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.
