Saturday, October 31, 2015

How to find Time Complexity of an Algorithm

Labels: ,
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).

main(){
 int a=10,b=20,sum; //constant time, say c1
 sum = a + b; //constant time, say c2
}
The time complexity of the above program = O(1)

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 =  c1 + c2 
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) = n3 + 25n2 + n + 10
the upper bound of f(n) is n3. That means n3 gives the maximum rate of growth for f(n) at larger values of n. Therefore f(n) = O(n3)


Lets us return back to determine the time complexity.

See another example:
for(i=1; i<=n; i++)
       sum = sum + 2; // constant time, c
 The 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, c
Here we can see that the value of i is doubling on every iteration. i.e At first iteration i = 2, second iteration i = 4, third iteration i = 8. Assume that at kth iteration, value of i reaches n. That is, 2k = n

Taking log on both sides we get
log(2k) = log n
k 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 = cn2 = O(n2)

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 + en2 = O(n2)

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 + dn2 + e n = O(n2)

21 comments:

  1. AnonymousJuly 20, 2016 at 10:59 PM

    how to calculate complexity of a program using C program?
    I know how to calculate it theoritically, but unable to implement it in C program itself. please suggest some method. THANK YOU!

    ReplyDelete
    Replies
    1. AnonymousDecember 24, 2016 at 8:35 AM

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

      Delete
  2. UnknownOctober 16, 2016 at 1:34 AM

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

    for(int i=0;i<n;i++)
    {
    for(int j=0;j<=i;j++)
    {
    sum++;
    }
    }

    what is time complexity of this program?

    ReplyDelete
  3. UnknownFebruary 4, 2017 at 7:41 AM

    O(n2) because

    for(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).

    ReplyDelete
  4. UnknownJuly 8, 2017 at 3:40 PM

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

    ReplyDelete
  5. UnknownAugust 17, 2017 at 9:21 AM

    what is the complexity for following program

    for(i=0; i<n;)
    i=i*k;

    assuming k to be a constant.

    ReplyDelete
  6. UnknownJanuary 8, 2018 at 8:36 PM

    Hii...please find the time complexity of this algorithm..

    1) Sort the received data set, X , in ascending order.
    2) Divide the set X into two halves, lower half, X[LH]
    and upper half, X[UH]. Let X[LH] =(L1 < L2 < L3 ...... Lh) and X[UH] =(U1
    < U2 < U3 ...... Uh)
    3) For each half, X[LH] and X[UH] , calculate the gaps
    between successive data points.
    4) Find the position of the largest gap, Pos[LH] , from the
    set X[LH] for finding the lower outlier.
    5) Similarly, find the position of the largest gap, Pos[UH],
    from the set X[UH] for finding the upper outlier.
    6) The number of data points to the left of the Pos[LH]
    are the detected lower outlier and the number of
    data points to the right of the Pos[UH], are the detected
    upper outliers

    ReplyDelete
  7. UnknownJuly 31, 2018 at 7:05 AM

    👌👌thanks

    ReplyDelete
  8. UnknownAugust 17, 2018 at 1:10 PM

    i have a question can u solve
    1. Calculate the Time complexity of the Algorithm below:
    A()
    {
    int I,j,k;
    for(i=n/2;i<=n;i++)
    for(j=1;j<=n;j=2*j)
    for(k=1;k<=n;k=k*2) printf(“KLEF”);
    }

    ReplyDelete
  9. smadhuAugust 31, 2018 at 11:45 AM

    {
    int I,j,k;
    for(i=n/2;i<=n;i++)
    for(j=1;j<=n;j=2*j)
    for(k=1;k<=n;k=k*2) printf(“KLEF”);
    }

    ReplyDelete
  10. AnonymousApril 29, 2019 at 10:05 AM

    ,,,,,,,,,,,,,,,,,,,

    ReplyDelete
  11. UnknownAugust 3, 2019 at 4:50 PM

    Find the complexity of the below program:
    function(int n)
    {
    if (n==1)
    return;
    for (int i=1; i<=n; i++)
    {
    for (int j=1; j<=n; j++)
    {
    printf("*");
    break;
    }
    }

    ReplyDelete
  12. UnknownAugust 3, 2019 at 4:50 PM

    ans for the above question

    ReplyDelete
  13. UnknownJune 7, 2020 at 10:00 AM

    using namespace std;
    int number_of_disc_intersections(vector &v) {
    int MAX_INTERSECTIONS = 10000000;
    size_t v_size = v.size();
    vector start(v_size, 0), end(v_size, 0);
    for (size_t i = 0; i < v_size; ++i) {
    start[max(0, static_cast(i) - v[i])]++;
    end[min(v_size - 1, i + v[i])]++;
    }
    int active = 0;
    int intersections = 0;
    for (size_t i = 0; i < v_size; i++) {
    intersections += active * start[i] + (start[i] * (start[i] - 1)) / 2;
    if (intersections > MAX_INTERSECTIONS) {
    return -1;
    }
    active += start[i] - end[i];
    }
    return intersections

    ReplyDelete
  14. AnonymousAugust 22, 2020 at 3:00 AM

    What is the time complexity of the following two exponential functions

    int exp1 (int a, int b){

    int ans =1;

    while(b>0){

    ans *= a;

    b-=1;

    }



    return ans;

    }

    int exp2 (int a, int b){

    if b==1;

    return a;

    else

    return a*exp2(a,b-1);

    }

    ReplyDelete
  15. AnonymousOctober 30, 2020 at 3:07 AM

    How do you find the complexity of
    f(x) = log(x)?
    I have seen a lot of examples that end with O(log(x)), but none that go the other way around.

    ReplyDelete
  16. UnknownDecember 23, 2020 at 2:34 AM

    inputFile = open('InputPS4.txt','r')
    """reading the input value from text file"""
    fileLines = inputFile.readlines()
    val=fileLines[0].split(":")
    """reading the first line of the input text file and split the strings and variables"""
    call = fileLines[1].split(":")
    """reading the line of the input text file and split the strings and variables"""
    ideal= fileLines[2].split(":")
    fileLines = [str.strip(val[1]),str.strip(call[1]),str.strip(ideal[1])]
    n = int(fileLines[0])
    call = [int(i) for i in fileLines[1].split(" ")]
    ideal = [int(i) for i in fileLines[2].split(" ")]
    i=0
    res = 0

    while(len(call) > 0):
    while(call[0] != ideal[0]):
    print( "push: ",call[0], file=open("OutputPS4.txt", "a"))

    call = call[1:] + call[:1]
    res += 1

    if(call[0] == ideal[0]):
    ideal.pop(0)
    print( "pop: ",call[0], file=open("OutputPS4.txt", "a"))
    call.pop(0)

    res += 1
    print( "Total time: ",res, file=open("OutputPS4.txt", "a"))

    ReplyDelete
  17. Cracking the coding interviewMarch 16, 2021 at 4:19 PM

    The efficiency of an algorithm is determined by time complexity, the upper bound is often estimated for this purpose. Algorithms, Data structures, and system design are essential to cover when preparing for interviews. Find system design interview questions. Great blog.

    ReplyDelete

Subscribe to: Post Comments (Atom)