Exercises

1. Consider the function . Using Definition  show that .
2. Consider the function . Using Definition  show that .
3. Consider the functions and . Using Theorem  show that .
4. Consider the functions and . Using Theorem  show that .
5. For each pair of functions, f(n) and g(n), in the following table, indicate if f(n)=O(g(n)) and if g(n)=O(f(n)).

   f(n)	g(n)
   10n

6.   Show that the Fibonacci numbers (see Equation ) satisfy the identities

   

   for .

7. Prove each of the following formulas:
   1. 
   2. 
   3. 
8. Show that , where and .
9. Show that .
10. Solve each of the following recurrences:
    1. 
    2. 
    3. 
    4. 
11. Derive tight, big oh expressions for the running times of sum.c,horner.c,factorial.c,findmax.c,geometric.c,geometric2.c,power.c,geometric3.c.
12. Consider the C++ program fragments given below. Assume that n, m and k are unsigned ints and that the functions e, f, g and h have the following characteristics:
    • The worst case running time for e(n,m,k) is O(1) and it returns a value between 1 and (n+m+k).
    • The worst case running time for f(n,m,k) is O(n+m).
    • The worst case running time for g(n,m,k) is O(m+k).
    • The worst case running time for h(n,m,k) is O(n+k).
    Determine a tight, big oh expression for the worst-case running time of each of the following program fragments:

    1. f (n, 10, 0);
       g (n, m, k);
       h (n, m, 1000000);

    2. for (unsigned int i = 0; i < n; ++i)
           f (n, m, k);

    3. for (unsigned int i = 0; i < e (n, 10, 100); ++i)
           f (n, 10, 0);

    4. for (unsigned int i = 0; i < e (n, m, k); ++i)
           f (n, 10, 0);

    5. for (unsigned int i = 0; i < n; ++i)
           for (unsigned int j = i; j < n; ++j)
               f (n, m, k);

13.   Consider the following C++ program fragment. What value does f compute? (Express your answer as a function of n). Give a tight, big oh expression for the worst-case running time of the function f.

    unsigned int f (unsigned int n)
    {
        unsigned int sum = 0;
        for (unsigned int i = 1; i <= n; ++i)
            sum = sum + i;
        return sum;
    }

14.   Consider the following C++ program fragment. (The function f is given in Exercise ). What value does g compute? (Express your answer as a function of n). Give a tight, big oh expression for the worst-case running time of the function g.

    unsigned int g (unsigned int n)
    {
        unsigned int sum = 0;
        for (unsigned int i = 1; i <= n; ++i)
            sum = sum + i + f (n);
        return sum;
    }

15. Consider the following C++ program fragment. (The function f is given in Exercise  and the function g is given in Exercise ). What value does h compute? (Express your answer as a function of n). Give a tight, big oh expression for the worst-case running time of the function h.

    unsigned int h (unsigned int n)
        { return f (n) + g (n); }

Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.