CODEWITHSUNDEEP
time-complexity
Ilia Labkovsky
Ilia Labkovsky

Reputation: 31

Comparing the big-O and big-Omega of functions

I can find the big-O and big-Omega of functions but it is hard for me to check if a certain function is the big-O or big-Omega of another one. for example:

Is n^(1/2) the big-O or big-Omega of n^(2/3)?
Is log(5n) the big-O or big-Omega of 10log(n)?

I'm unsure how to compare them beyond just using a graphing calculator. Can someone direct me to a resource that provides techniques on comparing the growths of functions?

Upvotes: 1

Views: 591

Answers (1)

Dimitar
Dimitar

Reputation: 4783

First one is trivial, you just compare the powers, so a = n^(1/2) <= b = n^(2/3). Therefore you a is in O(n^(2/3)) and analog b is in Omega(n^(1/2)).

For the second, you need the logarithm rules, which give you

log(5n) = log(5) + log(n)

//Since log(5) is constant
log(n) < 10log(n) //wait, 10 also

==> asymptotic equally growing, both in Theta

As a check-up tool, you can take a look at Wolfram|Alpha.

You can also use the limit of their quotient for n to infinity when the function are more complex to check it. For example to see for n! and n^n.

A quick reference for most common functions.

Hope it helps!

Upvotes: 1

Related Questions