Python Forum

Hi, I'm reading the DS & Algorithms book in Python by Goodrich, Tamassia, and Goldwasser published by Wiley ©2013. This isn't homework, I'm just studying for interviews. I don't understand their Example 3.15 on page 127 regarding their explanation of Big-Omega. Does anyone understand the math used here? See problem below:

By definition,
f(n) >= cg(n), for n >= n0

(c is a real number greater than zero, and n is an integer greater than or equal to one, we can also assume the base is 2.)

Example 3.15:
3n log n - 2n is big-omega(n log n)

Justification:
3n log n - 2n = n log n + 2n(log n - 1) >= n log n for n >= 2; hence, we can take c = 1 and n0 = 2 in this case.

I don't understand how the authors went from 3n log n - 2n = n log n + 2n(log n - 1) , and why the authors choose n=2 instead of n=1. Could you explain how the authored did the math, and why they chose n=2?

I tried looking at the Logarithm Rules and examples on page 116, but they don't seem to apply here. I also looked at the examples for Big-Oh notation on page 125, the book says Big-Oh notation allows us to ignore constant factors and lower order terms, but I still don't understand what the authors were doing in the justification. Thanks.

Here's an explicit set of steps to reach n log n + 2n(log n - 1):
3n log n - 2n = (n + 2n)(log n) + n - 2n
3n log n - 2n = n log n + 2n log n - 2n
3n log n - 2n = n log n + 2n(log n - 1)
Since 2n(log n - 1) >= 0 for n >= 1
3n log n - 2n >= n log n

Not sure why they would use n = 2 instead of n = 1. Both work well.

(May-28-2020, 06:02 PM)sheeba_weeba Wrote: [ -> ]Here's an explicit set of steps to reach n log n + 2n(log n - 1):
3n log n - 2n = (n + 2n)(log n) + n - 2n
3n log n - 2n = n log n + 2n log n - 2n
3n log n - 2n = n log n + 2n(log n - 1)
Since 2n(log n - 1) >= 0 for n >= 1
3n log n - 2n >= n log n

Not sure why they would use n = 2 instead of n = 1. Both work well.

Thanks Sheeba!!