CODEWITHSUNDEEP
big-oasymptotic-complexity
user5880385
user5880385

Reputation:

Show Asymptotic relationships using definitions

I am very solid at the understanding of definitions of Big-O notation along with Big-Omega and big-Theta notation. However, I struggle with actually determining through proof based reasoning using the actual definitions.

In an example that would ask:

Show 8n3 logn + 14n2 = θ(n3 logn).

I know that polynomials dominate logarithmic functions in terms of growth rate and that when determining asymptotic relationships one can ignore lower order terms such as the 14n2. But how can I show this concretely using the definition of asymptotic notations as the problem asks?

Upvotes: 1

Views: 283

Answers (1)

Bill the Lizard
Bill the Lizard

Reputation: 405745

If you want to prove what you found informally (by ignoring the coefficient of the highest-order term and throwing away the lower order terms), that

8n3 log(n) + 14n2 = θ(n3 log(n))

you have to find some positive constants c1, c2, and n0 such that

c1n3log(n) <= 8n3log(n) + 14n2 <= c2n3log(n)

for all n >= n0.

You can simplify the inequality by dividing by n3log(n) to get

c1 <= 8 + 14/nlog(n) <= c2

Now it's relatively straightforward to choose values that will make the inequalities always hold true. Start with n=2 and compute the middle portion of the inequality, then choose values for c1 and c2. (In this case, you want to be careful to avoid n=1, because then you'd be dividing by 0.) There are lots of values that will work. Say c1=1 and c2=15, and plug those in to the original inequality to see if it holds true for all values of n >= 2.

Upvotes: 1

Related Questions