Thread: Time complexity.

  1. #1
    Registered User
    Join Date
    Apr 2015
    Posts
    500

    Time complexity.

    I'm still not totally skilled to find the time complexity so bear with me and be on touch with me to the end please.
    I've three examples over here, but don't know actually how exactly to find the time's complexity, I know how to goes, but practically how to find is still doubted me.

    First example:
    Code:
    void f(int n)
    {
     int j, s;
     for(j=0, s=1; s<n; j++,s*=2)
     printf(“!”);
     double values[j];
     for(int k=0; k<j; k++)
     values[k]=0;
     while(j--)
     for(int k=1; k<j; k++)
     values[k]+=1.0/k;
    }
    the time complexity for it should be : O(log^2(n))
    Code:
    void f(int n){ for (int i=1; i<=n; i++) for (int j=1; j<=n*n/i; j+=i) printf(“*”);}
    the time complexity for it should be : O(n^2)
    Code:
    void g(int n, int i){
     if(i*i>n) return; g(n, i+1); printf(“#”);
    }
    void f(int n){ g(n, 0); g(n, n/2);}
    the time complexity for it should be : O(sqrt(n)).



    I know there's algorithm for calculating the complexity, and I already known of it, but how practically it goes on codes isn't totally understood for me, so if you can give me hints why those answers of three examples step by step are correct then thanks in advance and much appreciated.

  2. #2
    Programming Wraith GReaper's Avatar
    Join Date
    Apr 2009
    Location
    Greece
    Posts
    2,632
    Let's take a look at your first example:

    The first loop is simply O(log(n)). The saved integer "j" is also approx. log(n).

    The second loop is O(j), which is O(log(n)).

    The third loop combo's steps are:
    j*(j+1)/2 ↔ (j˛ + j)/2 ↔ log˛(n)/2 + log(n)/2

    Since in complexity we mostly care about what happens then "n" gets very large, we simply discard the rest and say O(log˛(n)).
    Devoted my life to programming...

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Time complexity of algorithm
    By viblic in forum C Programming
    Replies: 2
    Last Post: 01-11-2012, 11:22 AM
  2. question about code's time complexity
    By nik in forum C++ Programming
    Replies: 2
    Last Post: 03-06-2011, 03:21 PM
  3. Time Complexity
    By Stuart Dickson in forum C Programming
    Replies: 7
    Last Post: 07-20-2010, 03:13 AM
  4. measure time complexity
    By l2u in forum C++ Programming
    Replies: 1
    Last Post: 11-14-2008, 08:07 AM
  5. question on time complexity
    By blue_gene in forum C++ Programming
    Replies: 10
    Last Post: 05-16-2004, 05:09 AM