Big Oh Notation Finding n0 and c

user_15300873 0
Viewed 122

I was looking at this question:

Prove that 100+5 ∈ (²) (Which is 100+5 is upper bounded by ²)

() ≤ () for all ≥ 0
so it becomes 100+5 ≤ ²

The answer was:

0 ≈ 25.05 (the number where the ² algorithm intercepts the algorithm) and = 4 so that when increases above 25.05 no matter what it will still prove that 100+5∈² is true

My question is: how do you derive that 0 = 25.05 and = 4? Is it a guess and trial method, or is there a proper way to get that particular answer? Or you just gotta start from 1 and work your way up to see if it works?

discrete-mathematics computer-science structure algorithm
2 Answers

A good approach to tackle such kind of problems is to first fix the c let's take 4 in this example

and then all you have to do is figure out n0 using a simple equality

100n + 5 = 4n^2 <=> 4n^2 - 100n - 5 = 0 <=> n = 25.05 or n = -0.05 and here you can remark that they intersect twice in -0.08 and 25.05 and as you want n0 such that after which 100n +5 is always below 4n^2 -0.05 is not the one as 25.05 > -0.05 and in 25.05 they intersect so n0 = 25.05 .

Before fixing c and trying to figure out n0 you could try big numbers for n0 to have an idea whether it's an upper bound or not.

user_149276190

There are infinitely many choices for n0 and c that can be used to prove this bound holds. We need to find n0 and c such that for n >= n0, f(n) <= c * g(n). In your case, we need 100n + 5 <= cn^2. We can rearrange this as follows using basic algebra:

cn^2 - 100n - 5 >= 0

We can use the quadratic formula to find the roots:

n1, n2 = [100 +- sqrt(10000 + 20c)]/2c

Because c is positive we know the sqrt term will be greater than 100 once evaluated and since we are only interested in n > 0 we can discard the smaller of these solutions and focus on this:

n0 = [100 + sqrt(10000 + 20c)]/2c

We can simplify this a bit:

n0 = [100 + sqrt(10000 + 20c)]/2c
   = [100 + 2*sqrt(2500 + 5c)]/2c
   = [50 + sqrt(2500 + 5c)]/c

At this point, we can choose either a value for c or a value for n0, and solve for the other one. Your example chooses c = 4 and gets the approximate answer n0 ~ 25.05. If we'd prefer to choose n0 directly (say we want n0 = 10) then we calculate as follows:

10 = [50 + sqrt(2500 + 5c)]/c
10c = 50 + sqrt(2500 + 5c)
(10c - 50) = sqrt(2500 + 5c)
(100c^2 - 1000c + 2500) = (2500 + 5c)
100c^2 - 1005c = 0
c(100c - 1005) = 0
c = 0 or c = 1005/100 ~ 10.05

Because the solution c=0 is obviously no good, the solution c ~ 10.05 appears to work for our choice of n0 = 10. You can choose other n0 or c and find the corresponding constant in this way.

user_8472690
Related