26

I am trying to solve this recurrence

T(n) = 3 T(n/2) + n lg n ..

I have come to the solution that it belongs to masters theorem case 2 since n lg n is O(n^2)

but after referring to the solution manual i noticed this solution that they have

enter image description here

The soluttion says that n lg n = O ( n ^(lg 3 - e)) for e between 0 and 0.58

so this means n lg n is O(n) .. is this right? Am i missing something here?

Isn't nlgn O(n^2) ?

Majid
  • 13,853
  • 15
  • 77
  • 113
Wael Awada
  • 1,506
  • 3
  • 18
  • 31

3 Answers3

99

This will explain things better enter image description here

Sreenath Nannat
  • 1,949
  • 1
  • 13
  • 18
  • 3
    thanks for the effort .. So I guess n lg n > O(n) .. and the book is wrong? – Wael Awada Oct 20 '11 at 03:32
  • @WaelAwada The book's answer does not contradict O(n log n) > O(n). – Ilian Oct 20 '11 at 03:40
  • @WaelAwada The excerpt from the book looks a written form (if unfortunate for swapping first and second term) for: _We_ have two terms to consider for stating simple dominating functions: _n lg n_ and _n^logb a_. Since _n lg n_ is dominated by _n to the power of **anything** larger than one_, it is dominated by _n^lg 3_. – greybeard Nov 14 '14 at 08:16
  • 4
    Did you take that chart from here? http://bigocheatsheet.com You should credit your source! – Lukas Eder May 12 '16 at 14:26
  • That chart's purple line for O(nlogn) is wrong. Look at 100 on the x-axis. It should map to 100*log(100) = 100*2 = 200. Instead it maps to approximately 650 in the chart. Maybe they're throwing in a constant multiplier, but they didn't do it for the other lines. Weird. – Anssssss Mar 07 '17 at 20:42
  • 1
    It is Log2(100) ~ 7 – cognacc Apr 14 '17 at 10:49
15

n*log(n) is not O(n^2). It's known as quasi-linear and it grows much slower than O(n^2). In fact n*log(n) is less than polynomial.

In other words:

O(n*log(n)) < O(n^k)

where k > 1

In your example:

3*T(2n) -> O(n^1.585)

Since O(n^1.585) is polynomial and dominates O(n*log(n)), the latter term drops off so the final complexity is just O(n^1.585).

Mysticial
  • 464,885
  • 45
  • 335
  • 332
6

nlg3 is not O(n). It outgrows O(n)... In fact, any exponent on n that is larger than 1 results in an asymptotically longer time than O(n). Since lg(3) is about 1.58, as long as you subtract less than .58 from the exponent it is asymptotically greater than O(n).

  • So if i understand correctly, you, like me, are thinking the solution manual is wrong by saying n lgn = O(n) – Wael Awada Oct 20 '11 at 03:30
  • No! n log n is bigger, outgrows, and is NOT bounded by n. It's the other way around. –  Oct 20 '11 at 03:31
  • f(n) = O(g(n)) if f(n) < c.g(n) for for all n > n0 .. so if n lg n = O(n) what would c and n0 be ? – Wael Awada Oct 20 '11 at 03:37
  • Let c = 1 and n0 be 5, and you'll see that it's NOT TRUE. The other way around is. –  Oct 20 '11 at 03:45
  • so if the other way around is then n = O(n lg n) which I understand but the book is saying n lgn = O (n) – Wael Awada Oct 20 '11 at 03:54