Data Structures and Algorithms with Object-Oriented Design Patterns in C++

# 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:
8. Show that , where and .
9. Show that .
10. Solve each of the following recurrences:
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.