CODEWITHSUNDEEP
algorithmmathlogging
ProgramingGeek
ProgramingGeek

Reputation: 63

Calculation of log for efficiency in math

Hello I am weak in maths. but I an trying to solve the problem below. Am I doing it correctly>

Given: that A is big O, omega,or theta of B.

Question is:

A = n^3 + n * log(n);

B = n^3 + n^2 * log(n);

As an example, I take n=2.

A= 2^3+2log2 => 8.6

B= 2^3+2^2log2 => 9.2

A is lower bound of B..

I have other questions as well but i need to just confirm the method i am applying is correct or is there any other way to do so.

Am doing this right? Thanks in advance.

Upvotes: 0

Views: 113

Answers (2)

Lutz Lehmann
Lutz Lehmann

Reputation: 25992

 A     n^3 + n  *log(n)     1 + log(n)/n^2
--- = ------------------ = ----------------
 B     n^3 + n^2*log(n)     1 + log(n)/n

Since log(n)/n and also log(n)/n^2 have limit zero for n trending to infinity, the expressions 1+log(n)/n and 1+log(n)/n^2 in the canceled quotient A/B are bounded to both sides away from zero. For instance, there is a lower bound N such that both expressions fall into the interval [1/2,3/2] for all n > N. This means that all possibilities are true.

Upvotes: 0

soegaard
soegaard

Reputation: 31147

The idea behind the big O-notation is to compare the long term behaviour. Your idea (to insert n=2) reveals whether A or B is largest for small values of n. However O is all about large values. Part of the problem is to figure out what a large value is.

One way to get a feel of the problem is to make a table of A and B for larger and larger values of n:

           A       B
n=10
n=100
n=1000
n=10000
n=100000
n=1000000

The first entry in the table is A for n=10: A=10^3 + 10*log(10) = 1000+10*1 = 1010.

The next thing to do, is to draw graphs of A and B in the same coordinate system. Can you spot any long term relation between the two?

Upvotes: 1

Related Questions