Give an example of a function f such that fn On2 and fn n

Give an example of a function f such that:

f(n) = O(n2) and f(n) = (n), but f(n) = (n2) and f(n) = (n).

Prove your answer.

Solution

Let s(i, j) be the maximum number of coins that can be collected when Pac-Man reaches cell (i, j). Then s can be defined recursively as follows: s(i, j) = ( max{s(i 1, j), s(i, j 1)} + Mi,j (i 1, j 1) 0 (i = 0 or j = 0) where we extend the domain of s to include i = 0 or j = 0, for convenience. Thus we can use dynamic programming to compute s(i, j) for all i, j, e.g. proceed by the rows. Once we have computed all s(i, j), we can recover the optimal path by tracing backwards from (n, n); at each cell (i, j), we move upward or leftward, depending on which of s(i 1, j) and s(i, j 1) is larger

If f(n) is O(g(n)) then
   there exist a constant c > 0, and a constant n₀ such that for all n n₀: f(n) c*g(n)

hence:
   there exist a constant c > 0, and a constant n₀ such that for all n n₀: g(n) (1/c)*f(n)
     note that since c > 0, then the constant (1/c) > 0

hence:
   there exist a constant k > 0, namely k = (1/c), and a constant n₀ such that for all n n₀: g(n) k*f(n)

which is the definition of g(n) = (f(n)).