Exercises 3.1-8

Ω(g(n,m)) = {f(n,m): there exists positive constant c, , and such that 0 ≤cg(n,m) ≤ f(n, m)  for all n ≥ and m ≥ .

Θ(g(n,m)) =  Ω(g(n,m))∩O(g(n,m))

Exercises 3.1-7

If f(n)=o(g(n)), then f(n)/g(n)=0, when n→ ∞. If f(n) = ω(g(n)), then f(n)/g(n)=∞, when n→ ∞. So f(n) can’t equal to both o(g(n)) and ω(g(n)).

Exercises 3.1-6

If the running time is Θ(g(n)), it means that the algorithm can run at most O(g(n)), And the algorithm run at least Ω(g(n)). Since worst case is the longest running time, and best case is the fastest running time. So worst case must be O(g(n)), and best case must be Ω(g(n)).

Exercises 3.1-5

Because f(n)=O(g(n)), then there exists constants a and b, such that f(n) ≤ ag(n) for all n > b.
f(n) = Ω(g(n)), then there exists constants c and d, such that f(n) ≥ cg(n) for all n > d.
Then we can get, cg(n) ≤ f(n) ≤ ag(n) for all n > max(b, d).

The proof of other direction is also easy.

Exercises 3.1-4

= , because .

is not , because . That means = .

Exercises 3.1-3

Since the running time is at least f(n) menas the lower bound. But big-O means the upper bound, so we still don’t know the actually lower bound.

Exercises 3.1-2

= = =

Exercises 3.1-1

Suppose that f(n) is larger than g(n) asymptotically. Then max(f(n), g(n)) = Θ(f(n)) = Θ(f(n) + g(n))