CODEWITHSUNDEEP
algorithmbig-o
grooot
grooot

Reputation: 466

Theta notation for polynomial - Fundamental Algorithms

What is the Theta notation for the below function:

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

Any suggestion would be great!!!

Upvotes: 0

Views: 123

Answers (1)

MBo
MBo

Reputation: 80197

This expression for large n values (n → ∞) is asymptotically equivalent to 1/n

To check that f(n) is equivalent to g(n), we have to show that limit of their ratio is constant:

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

so

limit(f(n)/(1/n))[n → ∞] = 1 - 0 + 0 = 1

and f(n) is asymptotically equivalent to 1/n

Upvotes: 1

Related Questions