Use limit theorems to compare each pair of functions below F

Use limit theorems to compare each pair of functions below. For each pair, determine if:

f(n) = (g(n)) or
f(n) = O(g(n)) but f(n) = (g(n)) or
f(n) = (g(n)) but f(n) = (g(n))

(a) f(n) = n^0.3 and g(n) = n^0.5

(b) f(n) = 2^n+5 and g(n) = 4^n

(c) f(n) = 3^2n and g(n) = 8^n+6

(e) f(n) = lg(n) and g(n) = n^1/2

(e) f(n) = lg(lg(n)) and g(n) = lg(n^2)

Solution

a) n^0.3 will be less than n^0.5 for sufficienty large n. So, f(n) = O(g(n)) for n >= 1

b)for sufficienly large n, 4^n will exceed 2^n + 5  So, f(n) = O(g(n)) for n >= 2

(c) f(n) = 3^2n and g(n) = 8^n+6

for n >= 2, f(n) is greter than g(n) So, f(n) = (g(n)) for n >= 2

d) f(n) = lg(n) and g(n) = n^1/2,

for x >= 0 , g(n) beats f(n) so f(n) = O(n)