Consider the computation of an for an integer n. A simple algorithm to compute i

Question

Consider the computation of an for an integer n. A simple algorithm to compute is the following:

result = 1;

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

result *= a;

9. How much time does the algorithm take in Big-O notation?

Here’s an improved algorithm:

result = a;

for(int i = 1; i <= k; i++)

result = result * result;

10. How much time does this algorithm take in Big-O notation?

Consider the following sequences:

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

k = k + 4;

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

for(j = 1; j <= 20; j++) {

k = k + i + j;

}

}

11. How much time does this algorithm take in Big-O notation?

Explanation / Answer

result = 1;

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

result *= a;

complexity: O(n)

explanation:

assignment and increment operations takes constant times..

and for loop runs n times..

so..O(n)

9)

result = a;

for(int i = 1; i <= k; i++)

result = result * result;

complexity: O(k)

explanation:

assignment and multiplication operations takes constant times..

and for loop runs k times..

so..O(k)

10)

for(j = 1; j <= 10; j++)//runs 10 times..

k = k + 4;//runs 10 times..

for(i = 1; i <= n; i++)//runs n times..

{

for(j = 1; j <= 20; j++)//runs 2o times.. for each i... means total n*20;

{

k = k + i + j;

}

}

complexity : 10+n*20 = O(n)

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects