CODEWITHSUNDEEP
big-oasymptotic-complexityupperbound
Muhammad Hamza
Muhammad Hamza

Reputation: 223

Find the bounds as tight as possible?

2^n −8 = O(2^n)
It says there are some positive constants c and n0 for which
0 <= f(n) <= cg(n) for all n >= n0

I solved it as:

2^n −8 <= c2^n
If c = 1, and n0 = 1
1-8 <= 1*1
-7<= 1
then for all n >= n0 it remains true.

which is true but I don't understand what is the meaning of Find the bounds as tight as possible ? Can anyone explain?

Upvotes: 0

Views: 2113

Answers (1)

meowgoesthedog
meowgoesthedog

Reputation: 15035

As tight as possible means finding a function g(n) with smallest order of growth such that it still satisfies f(n) = O(g(n)). In your example it is relatively straightforward (hence your confusion, I believe) - just remove everything but the fastest growing term (2^n).

However let's consider an example where the tightest bound might not be immediately obvious - the Fibonacci sequence generator: f(n) = f(n - 1) + f(n - 2). A simple way to find an upper bound would be to make an approximation, by replacing n - 2 with n - 1 to give f(n) ≈ 2 * f(n - 1), which is O(2^n). This is not the tightest bound though - by solving a quadratic equation you will find that the tightest bound is in fact Ө(1.61...^n) - see this page for more details.

Upvotes: 1

Related Questions