Question

Algorithms:

5) Is n^2 = Ω(nlog(n))? Show and prove (explain briefly in both cases; and if yes, show the proof and derive c and n_o).

Answer 1

f(n) = Ω(g(n)) means there are positive constants c and n0, such that f(n) >= cg(n) for all n ≥ n0

n^2 = Ω(nlog(n))

=>  n^2 >= c(nlog(n))
Let's assume c = 1
=>  n^2 >= c(nlog(n))
=>  n^2 >= 1(nlog(n))
=>  n^2 >= nlog(n)
=>  n >= log(n)

This above equation is true, for all n >= 1

so, n^2 = Ω(nlog(n)) for c = 1 and n0 = 1