## Pages

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. Nice article!

1. very useful article..:)

2. thanku for this article:)

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

4. 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

5. 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

6. 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

7. 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

8. 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

9. This comment has been removed by a blog administrator.

10. This comment has been removed by a blog administrator.