CODEWITHSUNDEEP
algorithmruntimebig-o
FluffyBeing
FluffyBeing

Reputation: 468

How to determine the runtime of this function

I'm having some trouble with basic runtime understanding, maybe someone can clarify for me. How would I go about determining the runtime of this function?

I need to determine rather f = O(g) or f = omega(g) or f = theta(g)

f(n) = 100n + logn
g(n) = n + (logn)2

So 100n and n are in the same order; and linear time > log time; at this point do I still need to look at the log part? Or can I determine that f = theta(g)?

Upvotes: 0

Views: 840

Answers (1)

Benjamin Gruenbaum
Benjamin Gruenbaum

Reputation: 276306

You can safely determine that they are the same order of magnitude. There is no need to look at the "log part".

Here is formal proof for this specific case, the general proof can be shown from limit arithmetic.

Let's look at the function h(n) = f(n)/g(n) as n approaches infinity, if it stays bounded above 0 and below some number m we know that f(x) = Theta(g(x)) (because of how Theta is defined).

So we have h(n) = (100n + logn)/(n + logn^2)

We know that if we show for that for any real x, it holds for Natural numbers too. So it is enough to show that for:

h(x) = (100x + logx)/(x + logx^2)

We know by l'Hospital's rule that if the derivatives of the nominator and denominator exist and converge than the limit of the original function exists and equals to the same number too. Let's apply that and get:

lim x-> infinity , h(x) = (100x + logx)/(x + logx^2) = 

lim x-> infinity , (100+1/x) / (1 + (2log(x) / x) )

We know that 1/x approaches 0 as x approaches infinity, and that (2logx)/x approaches 0 as x approaches infinity (in your words (time > log time)). So we get from limit arithmetic

lim x-> infinity h(x) = 100/1 = 100

Since the limit exists in R and is nonzero we get f(x) = Theta(g(x)) which is what we wanted to show.

Upvotes: 1

Related Questions