How to determine big "Oh" functions?

Question

Hey,

I managed to find the answers to these problems online, but that really doesn't help because I want to know how to do these, and I'm totally lost.. can someone show me the process for at least a few of these?

Which of the following are true and which are false, and why?

(a) √n^5 ∈ O(n^2)

(b) √n log √n ∈ O(n)

(c) log(n^3) ∈ O(n log n)

(d) 2/n + 4/n^2 ∈ Θ(1/n)

(e) (log_2(n))^.5 ∈ Θ(log(n))

(f) min(700, n^2) ∈ Θ(1)

How do I do these?

? · Accepted Answer

Its algebra and application of the rule for each "oh"

(a) √n^5 = n^5/2 = n^2.5. n^2.5>n^2, therefore, √n^5 is not ∈ O(n^2)

(b) log √n < √n < n, log √n < √n log √n < n log √n, therefore, √n ∈ O(n)

(c) log(n^3) = 3log(n), log(n log n) = log n + loglog n, 3 log(n) <= k log(n) <= log n +loglog(n), therefore, log(n^3) is ∈ O(n log n)

(d) 2/n + 4/n^2 = (n^2 + 4n)/n^3 = n(n+4)/n^3 < n/n < n/n^2 < n^2/n^3=1/n, therefore, 2/n + 4/n^2 ∈ Θ(1/n)

(e) (log_2(n))^.5 = .5 log_2 n = .5*k log n > log n > log log n, therefore, (log_2(n))^.5 is not ∈ Θ(log(n))

(f) 700 < n^2, 700 < k*1, 700 > l*1, l < k, therefore, min(700, n^2) ∈ Θ(1)

? · Answer

It's been a while since I've done one of these, but if I remember right, to find out if the Big Oh value is right you divide the left by the right and take the limit as n goes to infinity.

So for a:
lim (n^(5/2)/(n^2)) -> take the derivative of both using L'HÃ´pital's rule -> lim ((5/2)n^(3/2)/(2n)) -> lim((15/4)n^(1/2)/(2)) -> lim = â.

Because the limit is â, n^2 can't be a Big Oh value for ân^5.

The rest are done the same way.

How to determine big "Oh" functions?

2 Answers