1. Given the following formulas for algorithm efficiency, express each formula i

Question

1.       Given the following formulas for algorithm efficiency, express each formula in Big O notation:

          a. n2 + 5n

          b. 3n2 + 15n3

          c. 150n + 200

          d. the number of times a number n can be divided by 10 before dropping below 10.

          What is the Big O for each of the following code?

2.       for ( i = 0; i < n; i ++ )

          {   j += i; }

3.       for ( k = n; k > 0; k-- )

          {    j = k * 2;

                for ( j = 0; j < 2*n; j++ )

                              tot = tot + j * k;

          }

4.       i = n * n;

          while ( i > 0 )

          {   acc = acc + i * i;

               i = i / 2;

          }

5.    for ( i = 0; i < n; i ++ )

          {   j += i; }

          i = n * n;

          while ( i > 0 )

          {   acc = acc + i * i;

               i = i / 2;

          }

6.    for ( i = 0; i < n; i ++ )

          { k = n * n;

              while ( k > 0 )

             {   acc = acc + k * i;

                  k = k / 2;

             }

          }

Explanation / Answer

          a. n2 + 5n   O(n^2) since n^2 is the dominating factor when input size increases

          b. 3n2 + 15n3 O(n^3) since n^3 is the dominating factor when input size increases

          c. 150n + 200 O(n)    since n is the dominating factor when input size increases

          d. the number of times a number n can be divided by 10 before dropping below 10. O(e^n) Snce each time a number is divided we decrease by a value of exponent.

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

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