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

Answer:

1. theta ( n^4)

theta is tightest bound.. i.e also sometimes said as average case complexity.So for fn : 2n^4+n^2+1 ..we will have values around n^4

consider big values of n ...i.e n->infinity

2. nlog(n)

Similarly for 2nd we will have nlogn as highest term in expression.

3.

First loop executes (3n-1) and inner loop executes n so overall (3n-1)xn

so n^2

4. f(n) = omega( g(n))

which is c1* g(n) < = f(n) <= c2*g(n)

Now take the second case f(n) < = c2*g(n)

=> f(n) < = 1 * g(n)

=> f(n) <= g(n)

=> f(n) = O(g(n), proved.