fn n1 1n and gn n Note that fn equals 0 when n is odd an

f(n) = n(1 + (- 1)^n), and g(n) = n. Note that f(n) equals 0 when n is odd, and 2n when n is even. f(n) = o(g(n)) f(n) = O(g(n)) f(n) = Theta (g(n)) f(n) = Ohm (g(n)) f(n) = omega (g(n))

Solution

Solution: C - f(n)=theta(g(n))

Suppose f and g are functions from positive integers to positive integers. We can say f is O(g(n)) (read: \'\'f is order g\'\') if g is an upper bound on f: there exists a fixed constant c and a fixed n₀ such that for all nn₀,

f(n) cg(n).

Equivalently, f is O(g(n)) if the function f(n)/g(n) is bounded above by some constant.

o

We say f is o(g(n)) (read: \"f is little-o of g\'\') if for all arbitrarily small real c > 0, for all but perhaps finitely many n,

f(n) cg(n).

Equivalently, f is o(g) if the function f(n)/g(n) tends to 0 as n tends to infinity. That is, f is small compared to g. If f is o(g) then f is also o(g)

We say that f is (g(n)) (read: \"f is omega of g\") if g is a lower bound on f for large n. Formally, f is (g) if there is a fixed constant c and a fixed n₀ such that for all n>n₀,

cg(n) f(n)

For example, any polynomial whose highest exponent is n^k is (n^k). If f(n) is (g(n)) then g(n) is O(f(n)). If f(n) is o(g(n)) then f(n) is not (g(n)).

We say that f is (g(n)) (read: \"f is theta of g\") if g is an accurate characterization of f for large n: it can be scaled so it is both an upper and a lower bound of f. That is, f is both O(g(n)) and (g(n)). Expanding out the definitions of and O, f is (g(n)) if there are fixed constants c₁ and c₂ and a fixed n₀ such that for all n>n₀,

c₁g(n) f(n) c₂g(n)

For example, any polynomial whose highest exponent is n^k is (n^k). If f is (g), then it is O(g) but not o(g). Sometimes people use O(g(n)) a bit informally to mean the stronger property (g(n)); however, the two are different.