Question & Answer: Let f(n) = n lg n and g(n) = n^2. (a) Show that f(n) is O(g(n). (b) Argue that lg n/Squareroot n is O(…..

From defination, we know that Big-O notation denotes the upper bound or more formally a description of a function in terms of big O notation usually only provides an upper bound on the growth rate of the function.

1.
It is quite clear that nlogn grows less than n^2, so it is sensible saying
nlogn = O(n^2)
according to the defination provided above

red: n^2
blue: n*log(n)

2
Same goes here
We know that growth rate of (log n) < growthrate of (n)
similarlly growth rate of (log n/ sqrt(n)) < growthrate of (n/(sqrt(n))
or growth rate of (log n/ sqrt(n)) < growthrate of ((sqrt(n))

Simple mathematics! clear enough?

now according to defination we can say log n/sqrt(n) = O(sqrt(n))

so the stament is valid

3
As already said in question 1, growth rate of g(n) is more than growth rate of f(n) so g(n) is not O(f(n))

4.
f(g(n)) = n^2 log(n^2) = 2 n^2 log n
g(f(n)) = (n log n)^2 = n^2 log(n) * log(n)

So from the graph it is clear that growth rate of f(g(n)) < growth rate of g(f(n))

so it is valid that f(g(n)) > g(f(n))

red: g(f(n)) = n * n * log(n) * log(n)
blue: f(g(n)) = 2 * n*n * log(n)

5.
Since 4 is valid, 5 is not valid, quite obhious!