Question

.Prove that f(n) = 3logn + loglogn is capital omega (logn) , what is O(n)?

Answer 1

Answer:

The reason it boils down to log n is because as n gets larger, log(log(n)) increases slowly (try it on a calculator). 3log(n) is the one that really grows. But after a sad amount of iterations, the factor of 3 wouldn't matter. So, we say the BEHAVIOUR (or Big Omega Ω) of 3 log(N) + log(log(n)) is pretty much the same as log(n).

O(n) would also be 3 logn(n).

to understand this, we need to understand what these two notations mean. Ω is like a lower bound. It states that eventually, the function, for all values, will be greater than the Ω of that function. This is the blue line in the graph attached below. And O means that the function will remain inside, neither more nor less than the O notation.