The greatest mistake you can make in life is to be continually fearing you will make one

Monday 1 February 2010

Exercise for finding time complexity of an algorithm

Points to consider when analysing an Algorithm:
  1. A sequence of statements which is executed only once is O(1). It does not depends on how many statements are in the sequence.
  2. If a problem of size n can be solved with a simple loop
          for(i=0;i < n;i++)
             {statements;}
    where statements is an O(1) sequence of statements then the time complexity is n*O(1) or O(n)
  3. If we have 2 nested loops,
        for(j=0;j < n;j++)
            for(i=0;i < n;i++)
                 {statements;}
    then we have n repetitions of an O(n) sequence .so the complexity is n*O(n) which is O(n2)
  4. suppose if the inner loop depends on the outer loop index,
        for(j=0;j < n;j++)
            for(i=0;i < j;i++)
                 {statements;}
    The inner loop gets executed j times. so the total is n*(n+1)/2 times.so the complexity is O(n2). The result is same as the result for 2 nested loops.so the variable number of iterations of the inner loop doesnt affect.
  5. In a loop if a index jumps by an increasing amount in each iteration, such as
        n=1;
        while(n < =x)
        {
            statements;
            n=2*n;
        }
    in which n takes values 1,2,4,8..until it exceeds n.ie n=20,21,22,23.......This sequence has 1+Log2n values.so the complexity is O(log2n)
  6. If the number of iterations of the loops decreases by a constant factor with every iteration
        h=n;
        while(h > 0)
        {
            for(i=0;i < n;i++)
                statements;
            h=h/2;
        }
    then there are log2n iterations of the outer loop and n iterations of the inner loop. so the overall complexity is O(nlogn)
 Problems
  1. order the following functions by growth rate: n, root n, n1.5, n2, n log n, n log log n, n log2 n, n log(n2), 2/n, 2 , 2n/2, 37, n2 log n, n3. Indicate which functions grow at the same rate.
  2. In a heap with n elements with the smallest element at the root, the 7th smallest element can be found in time (GATE CS 2003)
    a) (n log n)
    b) (n)
    c) (log n)
    d) (1)
  3.  Programs A and B are analyzed and found to have worst-case running times no greater than 150n log2 n and n2, respectively. Answer the following questions if possible:
    a. Which program has the better guarantee on the running time, for large values of n (n > 10,000)?
    b. Which program has the better guarantee on the running time, for small values of n (n < 100)?
    c. Which program will run faster on average for n = 1,000?
    d. Is it possible that program B will run faster than program A on all possible inputs ?



11 comments:

  1. helped me a lot, thank you n keep going

    ReplyDelete
  2. Hi, I do believe this is an excellent blog. I stumbledupon it ;) I'm going to return yet again since i have book-marked it. Money and freedom is the best way to change, may you be rich and continue to guide others.

    my site: healthy diet plan
    Also see my webpage - healthy diet

    ReplyDelete
  3. Pretty nice post. I just stumbled upon your blog
    and wanted to say that I have truly enjoyed surfing around your blog posts.

    After all I will be subscribing to your rss feed and I
    hope you write again very soon!

    Have a look at my page: workouts for vertical jump

    ReplyDelete
  4. These are genuinely great ideas in on the topic of blogging.
    You have touched some pleasant points here. Any way keep up wrinting.


    Here is my webpage :: newport beach plastic surgery

    ReplyDelete
  5. You cannot wear a business suit and expect to be called cute.
    Try sending your loved one a short cute message or love poem
    telling him or her I love you. You could have a great relationship
    with your husband and boyfriend is a better word to use for him.
    Most people know that girls need to be told their worth and
    beauty on a regular basis. Especially wear clean shoes and
    your socks should not smell.

    Also visit my web page :: cute acrylic nail designs colored acrylic

    ReplyDelete
  6. video marrante VIDEO INSOLITE DROLE HUMOUR MARRANTE BUZZ CELA MEILLEUR DES VIDEOS bar drole
    Drole de gamelle Les video de celui-ci localisation perso appartiennent a leursauteurs respectifs.
    remède au volant vidéo drole Les video sur ces passage pas du tout
    m'appartiennent enjambée puis nenni sont foulée
    parmi hebergement surce localisation perso.
    Pub drole Wilkinson Bebe Divertissement de rôle
    drole au Quebec 8 Com'Z Voici cette vidéo cette
    davantage drôle jusqu'à ceci aurore inférieur YouTube !
    Excellente emprunt d’accident drole de cette vie quotidienne.
    Nous-même ne me lasse marche de regarder cette vidéo
    d’humour. Des condition droles puis rocambolesque dont peuvent vous arriver à vous encore.
    Pendant espérant qui’celui-là y ait un caméra au contraire
    virevolter ça! Gangnam Proportion, cette vidéo la davantage vue du Web alors cette davantage
    drôle de l'année? pub humour ferrari Aïeule fait du foot Vidéos davantage anciennes » chat fou

    My blog post: a mourir de rire

    ReplyDelete
  7. This comment has been removed by a blog administrator.

    ReplyDelete
  8. This comment has been removed by a blog administrator.

    ReplyDelete