Question

Use the limit method to prove the asymptotic relation between these 3 functions:

n 

2n

n^2

The limit method says that: lim (n --> infinity)  f(n) / g(n)   tends to 0, then f(n) = o(g(n)).  Similarly, if the limit tends to infinity, then f(n) = small omega (g(n)), and if the limit tends to a constant, then f(n) = theta (g(n)).

Answer 1

lim (n --> infinity)  n / 2n tends to 1/2 ; n = theta(2n)

 lim (n --> infinity)  n / n^2 , it will be 1/n and tends to 0 ; n = o(n^2)

 lim (n --> infinity)  2n / n^2 , it will be 1/n and tends to 0 ; 2n = o(n^2)