About 2T(n/2) + nlgn

[Haidong (Haydon) Xue]

It is maybe a common question about why we cannot use Master Theorem on 2T(n/2) + nlgn 

Since you see:

f(n)=nlgn

g(n)=n

f(n) = Omega(n)

And here is why:

Following the third rule of Mater Theorem, f(n) has to be lower bounded by n^(1+x), x>0, and you can never found a x that:

nlgn =  Omega (n^(1+x))

so, you cannot use Mater Theorem. 

--
Haidong(Haydon) Xue
Ph.D Candidate
Research Assistant, Teaching Instructor
Department of Computer Science
Georgia State University

http://www.cs.gsu.edu/~hxue1

[Charles Cole]

Did I miss someone saying if class was cancelled for July 4th?  I was just looking at the calendar for GSU:

Wednesday, July 04, 2012
All Day	(Cancelled) Daily Campus Visit
All Day	Library Hours - CLOSED
All Day	Registration for Fall 2012 (Multi-Day Event)
All Day	University Official Holiday (No Classes)
1:00 PM - 3:00 PM	Indian Creek Pool 4th of July Celebration

[Haidong (Haydon) Xue]

As I said in a previous message, we will have no class on July 4th too. I may update our schedule later.