Rules for Calculating Time Complexity andBig-Oh Rule 00 Normally these formulas

Question

Rules for Calculating Time Complexity andBig-Oh

Rule 00

Normally these formulas are very handy:

If then

Also,

Rule 0

The condition that stops a loop executes ONE MORE time than theloop itself (the last time is when it is evaluated false)

Rule 1

for (i=0;i<n;i=i+k)    Anything inside theloop will run approximately n/k times

Rule 2

for (i=n;i>0;i=i-k)    Anything inside the loop will run approximatelyn/k times

Rule 3

for (i=1;i<n;i=i*k)    Anything inside theloop will run approximately logkntimes

Rule 4

for(i=1;i<=n;++i)

for (j=1;j<=i;++j)

                                   The above nested loop approximately runs ½n(n+1) times.

                                   The variable j depends upon the value of i

Rule 5

for(i=1;i<=n;i=i*2)

for (j=1;j<=i;++j)

                                   The statements in the above nested loop approximately run2n-1 times.

                                   The variable j depends upon the value of i

Rule 6

If the loop variables are independent then the total times astatement inside a nested loop is executed is equal to the productof the times the individual loops run

e.g.      for (i=0;i<n;++i)

                       for (j=0;j<m;++j)

                                   A statement inside the above nested loop will runn*m times

Question # 1

[Marks: 10]

Find the running time complexity of the following pieceof code and show your working step by step.

x=0;

for (i=1;i<=n;i=i*2)

{           for(j=1;j<=2n;++j)

           {          

x=x+1;

           }

}

Question # 2

[Marks: 10]

Write the algorithm for Quick sort and calculate time T(n) for each step of the algorithm.

Explanation / Answer

[Marks: 10]

Find the running time complexity of the following pieceof code and show your working step by step.

x=0;

for(i=1;i<=n;i=i*2)                           it will go lg2n

{           for(j=1;j<=2n;++j)              it will go 2n times

           {          

x=x+1;                                //it will go 2nlg2n

           }

}

so complexity will be    O(n lg2n)

Question # 2

[Marks: 10]

Write the algorithm for Quick sort and calculate time T(n) for each step of the algorithm.

worst caseanalysis.

Related Questions

Navigate

• Browse (All)
• Browse R
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.