Big O: Determine value such that A is better than B for....

[Anood]

Algorithm A uses 20n·log(n) operations, while algorithm B uses n^3 .
Determine
the value n0 such that A is better than B for all n>=n0.
(”log” is log-base 2. You should solve this numerically)

20n·log(n)<=n^3

simplify

20 log(n)<=n^2

What should be done next?

 

[PAULK]

Hi, Linda,

>> Oops. Did you say your name was something else?

That's basically it, but now you just want to find the point at which the graphs of
y = 20 log2(n) and
y = n^2

intersect.

No calculators do base-2 logs by themselves, so we have to help them.

If x = log2(n), then n = 2^x
and 2 = e^ln(2). [ln is natural log.]

So n = [e^ln(2)]^x = e^[x ln 2]

So ln n = x ln 2 and x = ln n/ln 2 << Your basic rule; remember this.

So log2(n) = ln n/ln 2 and you want to solve the equation:

20 ln n/ln 2 = n^2

which, I think, you already knew. You just don't know how to solve it. The clue is the comment: You should solve this numerically.

A quick-and-dirty graph shows the graphs crossing at n0 between 7 and 8. Beyond that, the graph of n^2 is always bigger.

There are a number of numerical methods for getting a precise value, but if n is to be an integer, then n0 = 8 should certainly be the answer

Does this look familiar??