Question

Help here please

Show that 2n+1 is O(2n
) and 8n+5 = Ω(n)

Answer 1

Show that 2n+1 is O(2n)

Given f(n) = 2n+1

Definition of Big-Oh

f(n) = O(g(n)) means there are positive constants c and k, such that 0 ≤ f(n) ≤ cg(n) for all n ≥ k.

0 ≤ 2n+1 ≤ 2(2n)

Where c=2, n>0 and g(n)=2n

Step-by-step explanation:

So, from the definition of Big-Oh we can say that

f(n) = O(g(n)) = o(2n)