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 Example-a,Example-b,Example-c,Example-d,Example-f,Example-g,Example-h,Example-i.
12. Consider the Java program fragments given below. Assume that n, m, and k are non-negative ints and that the methods 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 (int i = 0; i < n; ++i)
           f (n, m, k);

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

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

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

13.   Consider the following Java 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 method f.

    class Example
    {
        static int f (int n)
        {
    	int sum = 0;
    	for (int i = 1; i <= n; ++i)
    	    sum = sum + i;
    	return sum;
        }
        // ...
    }

14.   Consider the following Java program fragment. (The method 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 method g.

    class Example
    {
        // ...
        static int g (int n)
        {
    	int sum = 0;
    	for (int i = 1; i <= n; ++i)
    	    sum = sum + i + f (i);
    	return sum;
        }
    }

15. Consider the following Java program fragment. (The method f is given in Exercise  and the method 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 method h.

    class Example
    {
        // ...
        int h (int n)
    	{ return f (n) + g (n); }
    }

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