p5.md

Problem

1. Rank the following functions by order of growth; that is, find an arrangement g₁, g₂, …, g₃₀ of the functions satisfying g₁ = Ω(g₂), g₂ = Ω(g₃), …, g₂₉ = Ω(g₃₀). Partition your list into equivalence classes such that functions f(n) and g(n) are in the same class if and only if f(n) = Ѳ(g(n)).
   
   
   
   
   
2. Give an example of a single non-negative function f(n) such that for all functions g_i(n) in part (a), f(n) is neither O(g_i(n)) nor Ω(g_i(n)).

Solution

1

2

We need a function f that looks like this:

when f grows faster then 2²ⁿ then f != O(any function above) because f = Ω(0), 0 is not in the candidates, we can simply choose