**Points to consider when analysing an Algorithm:**- A sequence of statements which is executed only once is
**O(1)**. It does not depends on how many statements are in the sequence. - 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)** - 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(n^{2}) - 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(n^{2}). The result is same as the result for 2 nested loops.so the variable number of iterations of the inner loop doesnt affect. - 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=2^{0},2^{1},2^{2},2^{3}.......This sequence has 1+Log_{2}n values.so the complexity is O(log_{2}n) - 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 log_{2}n iterations of the outer loop and n iterations of the inner loop. so the overall complexity is O(nlogn)

__Problems__

- 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.
- 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) - Programs A and B are analyzed and found to have worst-case running times no greater than 150n log2 n and n
^{2}, 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 ?

Nice article!

ReplyDeletevery useful article..:)

Deletethanku for this article:)

ReplyDeletehelped me a lot, thank you n keep going

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

ReplyDeletemy site: healthy diet plan

Also see my webpage-healthy dietPretty nice post. I just stumbled upon your blog

ReplyDeleteand 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

These are genuinely great ideas in on the topic of blogging.

ReplyDeleteYou have touched some pleasant points here. Any way keep up wrinting.

Here is my webpage :: newport beach plastic surgery

You cannot wear a business suit and expect to be called cute.

ReplyDeleteTry 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

video marrante VIDEO INSOLITE DROLE HUMOUR MARRANTE BUZZ CELA MEILLEUR DES VIDEOS bar drole

ReplyDeleteDrole 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

This comment has been removed by a blog administrator.

ReplyDeleteThis comment has been removed by a blog administrator.

ReplyDelete