Examples of Asymptotic analysis

Question

Here I will be giving two functions f(n) and g(n) and my aim is to decide if the f(n) is in theta, omega, big o, little o or little omega. Please provide detailed proof if you are confident with such problems.

Problem 1: f(n) = (1/2)n^2 - 3n, g(n) = n^2

Problem 2: f(n) = 6n^3, g(n) = n^2

Problem 3: f(n) = 3n+5, g(n) = n^2

Problem 4: f(n)= n ceiling(lg n^2), g(n)= n^2 log n

Problem 5: f(n) = [10^(n+4)(n)]+6, g(n)=10^(n+3)

Answer 1

Polynomial functions are easy. Just compare the highest order of each.

1. f(n) is n^2 and g(n) is n^2, thus f(n) is theta g(n)
2. f(n) is n^3 and g(n) is n^2, thus f(n) is O(g(n))
3. f(n) is n and g(n) is n^2, thus f(n) is W(g(n))

A proof would involve computing the limits.