CODEWITHSUNDEEP
algorithmbig-ocomplexity-theory
henryD
henryD

Reputation: 21

Θ-notation with (n^3.2)^-n in denominator

For a function like f(n) = 20n^2 + 5n + 7, the Θ-notation clearly is Θ(n^2).

But what about a more complex function where we have (n^3.2)^-n in the denominator?

f(n) = (n^2 + 2)/(1 + (n^3.2)^-n)

[![f(n) = (n^2 + 2)/(1 + (n^3.2)^-n)][1]][1]

Kindly explain the solution for better understanding.

Upvotes: 1

Views: 136

Answers (2)

Zabuzard
Zabuzard

Reputation: 25943

tl;dr

Yes, it is Θ(n²) as well.

Why?

f in Θ(g) is defined as f in O(g) and f in Ω(g) at the same time.

See the definition from Wikipedia:

Landau notation definitions

Your method f is

f(n) = (n^2 + 2)/(1 + ((n^3.2)^-n))

while g is just g(n) = n².

Now, informally, the denominator in f goes against 1 (1 + 0) since the -n grows extremely fast when going n ➝ ∞.

O(n²)

But step by step. Let us first deal with the simple direction, showing that f in O(n²).

You have to show that there is a constant factor k and a special starting value n₀ from which on, all n > n₀ will yield a smaller value. So that

f(n) ≤ k · g(n)

i.e.

(n^2 + 2)/(1 + ((n^3.2)^-n)) <= k * n^2

Now, that is quite simple since you can just estimate using ≤. The denominator is always positive and always greater 1 since the right part of the addition is always positive. Hence, it holds that you can just leave it away without making it bigger:

(n^2 + 2)/(1 + ((n^3.2)^-n)) <= n^2 + 2

and that is definitely smaller than k · n² if we set maybe k = 10, n₀ = 10.

Ω(n²)

The other direction is more tricky since now we have to show that f is actually bigger than k · n² despite the denominator making it smaller.

However, the tricky part in the denominator (n^3.2)^-n grows very fast against 0, informally because the -n is much stronger than n^3.2. Take a look at this plot:

plot (n^3.2)^-n

You can easily show that this is monotonically decreasing and going against 0, after the maxima at around n ≈ 0.36. So we can just take a higher value, such as n₀ = 10 and then we have the denominator under good control.

Now we can start the estimation with an upper bound:

(n^2 + 2)/(1 + ((n^3.2)^-n)) >= (n^2 + 2)/(1 + 10) >= n^2/(1 + 10) = 1/11 * n^2

So, we pick k = 1/11, n₀ = 10 and are done.

Θ(n²)

Since we just showed that f in O(n²) and f in Ω(n²), it follows that f in Θ(n²).

Upvotes: 1

user16830227
user16830227

Reputation: 76

It should be still O(n^2), right?

3.2^(-n) is getting infinitely close to 0 when n is increased. Then, the denominator is approximately 2 (= 1 + n^0).

Upvotes: 1

Related Questions