1 Give the most compact theta notation for the function 2n4

1. Give the most compact theta notation for the function 2n4 + n2 + 1.
2. Give the most compact theta notation for the function (2 lg n + 5)(7 + n).

3. Give the most compact theta notation for the number of times the statement
x = x + 1 is executed in the following pseudo-code:
                  for i = 1 to i = 3n 1{
                      for j = 1 to j = n{ x = x + 1

                               }
                    }

4. Let f (n) and g(n) be functions with domain {1, 2, 3, . . .}. Prove the fol-
lowing: If f (n) = (g(n)), then g(n) = O(f (n)).

5. Use the formulas s1 = 1 and sn = sn1 · n for n 2 to write a recursive algorithm
that computes

                                     sn = n!

You may use any style of pseudo-code to write your algorithm, but make sure that the
steps of your algorithm are clear.

Solution

Hi, I have answered first 3 questions for proper explanation:

According to asymptotic notation: we ignore lower order terms and constant multipliers

1. Give the most compact theta notation for the function 2n^4 + n^2 + 1.

   here 2n^4 > n^2 > 1
   so, ignoring n^2 and 1

   also 2 is constant multipliers in 2n^2, so ignoring 2 also

   Big-O: O(n^4)

2. Give the most compact theta notation for the function (2 lg n + 5)(7 + n).

   After multiplication:
       T(n) = 14logn + 2nlogn + 35 + 5n

       Here, 2nlogn > 5n > 14logn > 35

       Big-O= O(nlogn)

3. Give the most compact theta notation for the number of times the statement
x = x + 1 is executed in the following pseudo-code:

for i = 1 to i = 3n 1{
for j = 1 to j = n{
   x = x + 1
}
}

Here we have two for loops :
   outer for loop: runs for i=1 to i=3*n-1
   inner for loop:
       for each value of i, it runs j=1 to n, men n times

   so, t(n) = n + n+ n+ ..... (3*n-1) times
   t(n) = (3*n-1)*n
       = 3n^2 - n
   here, 3n^2 > n
   Big-O = O(n^2)