### Saturday, October 31, 2015

# How to find Time Complexity of an Algorithm

We can come up with several algorithms for a particular problem. But we need to choose the best algorithm that suits us. Hence we need to compare several algorithms and select the best algorithm.

Therefore, goal of analysis of algorithms is to compare algorithms with several factors like running time, memory, effort of developing, etc. Ideal factor to be selected for comparison purpose is running time of the algorithm which is a function of input size, n. Since running time is a function of input size it is independent of execution time of the machine, style of programming etc.

Below are some examples with the help of which you can determine the time complexity of a particular program (or algorithm).

How did we get O(1). First calculate the total time of each statement in the program (or algorithm). I have commented the time taken for each line. Why constant time? Because the statement to be executed does not depend on the input size. So it takes some constant execution time which depends on the machine. Since it does not depend on the input size we consider it as a constant time say c. So the total time taken by the program is

Total Time = c

Therefore Time Complexity = O(1)

What does Big-O Notation mean?

This notation gives the upper bound of a given function. for example, if

f(n) = n

the upper bound of f(n) is n

Lets us return back to determine the time complexity.

Here f(n) = nc, therefore Time Complexity = O(n)

Taking log on both sides we get

log(2

k log2 = log n

k = log n

Therefore time complexity = O(log n)

Therefore, goal of analysis of algorithms is to compare algorithms with several factors like running time, memory, effort of developing, etc. Ideal factor to be selected for comparison purpose is running time of the algorithm which is a function of input size, n. Since running time is a function of input size it is independent of execution time of the machine, style of programming etc.

Below are some examples with the help of which you can determine the time complexity of a particular program (or algorithm).

main(){ int a=10,b=20,sum; //constant time, say cThe time complexity of the above program = O(1)_{1}sum = a + b; //constant time, say c_{2}}

How did we get O(1). First calculate the total time of each statement in the program (or algorithm). I have commented the time taken for each line. Why constant time? Because the statement to be executed does not depend on the input size. So it takes some constant execution time which depends on the machine. Since it does not depend on the input size we consider it as a constant time say c. So the total time taken by the program is

Total Time = c

_{1}+ c_{2 }Therefore Time Complexity = O(1)

What does Big-O Notation mean?

This notation gives the upper bound of a given function. for example, if

f(n) = n

^{3}+ 25n^{2}+ n + 10the upper bound of f(n) is n

^{3}. That means n^{3}gives the maximum rate of growth for f(n) at larger values of n. Therefore f(n) = O(n^{3})Lets us return back to determine the time complexity.

__See another example:__for(i=1; i<=n; i++) sum = sum + 2; // constant time, cThe above code is a for loop. We know that the body of the for loop will be executed n times. Since the body of the loop consists of only one statement and since it takes only constant time c to execute the total time taken by the for loop is, Total time = nc

Here f(n) = nc, therefore Time Complexity = O(n)

__Another example:__for(i=1; i<=n; i++) i = i * 2; // constant time, cHere we can see that the value of

**is doubling on every iteration. i.e At first iteration i = 2, second iteration i = 4, third iteration i = 8. Assume that at k***i*^{th}iteration, value of*i*reaches*n*. That is, 2^{k}= nTaking log on both sides we get

log(2

^{k}) = log nk log2 = log n

k = log n

Therefore time complexity = O(log n)

__Another example:__for(i=1; i<=n; i++){ for(j=1; i<=n; i++) sum = sum + 2; // constant time, c }In the above code we can see nested loops. The inner loop iterates n times and outer loop iterates n time. Therefore, total time = c n n = cn

^{2}= O(n^{2})__Another example:__sum = a + b; //constant time, say c for(i=1; i<=n; i++) i = i * 2; // constant time, d for(i=1; i<=n; i++){ for(j=1; i<=n; i++) sum = sum + 2; // constant time, e }Total time = c + dn + en

^{2}= O(n^{2})__Another example:__if(i==1) //constant time for executing condition,c return false; //constant time, d else{ for(j=1; i<=n; i++) sum = sum + 2; // constant time, e }Total time = c + d + e n = O(n)

__Another example:__if(i==1) //constant time for executing condition,c return false; //constant time, d else for(j=1; i<=n; i++){ if(i>1) //constant time,f sum = sum + 2; //constant time, e }Total time = c + d + ( f + e ) n = O(n)

__Another example:__if(i==1){ //constant time for executing condition,c for(i=1; i<=n; i++) for(j=1; i<=n; i++) sum = sum + 2; // constant time, d }else{ for(j=1; i<=n; i++) sum = sum + 2; // constant time, e }Total time = c + dn

^{2}+ e n = O(n^{2})
Subscribe to:
Post Comments (Atom)

how to calculate complexity of a program using C program?

ReplyDeleteI know how to calculate it theoritically, but unable to implement it in C program itself. please suggest some method. THANK YOU!

I think the author has given some examples with which you can try to find the complexity of your program.

Deletei have question can you give me solution then plz..

ReplyDeletefor(int i=0;i<n;i++)

{

for(int j=0;j<=i;j++)

{

sum++;

}

}

what is time complexity of this program?

O(n2) because

ReplyDeletefor(int i=0;i<n;i++)

{

for(int j=0;j<=i;j++)

{

sum++; //constant time c

}

}

inner loop depends on the input n as its limit till 0 to n. and for time complexity we have to choose upper limit that is O(c*0+c*1+c*2.....+c*n)=O(n) and for whole program=O(n2).

func(inta[], int n){for(i=1;i<=n;i++) sum=sum+a[i];} find time complexity

ReplyDeletewhat is the complexity for following program

ReplyDeletefor(i=0; i<n;)

i=i*k;

assuming k to be a constant.