Go Back   TestMagic Forums > Test preparation > GRE Subject Tests > GRE Computer Science
Reload this Page How do I rigorously compute the average complexity for Quiksort?
Register Forum Rules FAQ Members List Calendar Search Today's Posts Mark Forums Read

Reply
 
LinkBack Thread Tools Search this Thread Display Modes
Old 2008 April 29th, 06:44 PM   #1 (permalink)
cda
I JUST got here.
 
Join Date: Apr 2008
Posts: 2
cda just joined TestMagic.
How do I rigorously compute the average complexity for Quiksort?
I know the average running time for Quicksort is O(n*log(n)). Can anyone provide a rigorous math proof to this. Ie, I how would determine the average complexity for Quicksort 1.39n * log_2 *n via recurrence relation?
cda is offline  
Digg this Post!Add Post to del.icio.usBookmark Post in TechnoratiFurl this Post!Google Bookmark this Post!Reddit!
Reply With Quote
Old 2008 April 29th, 11:05 PM   #2 (permalink)
cda
I JUST got here.
 
Join Date: Apr 2008
Posts: 2
cda just joined TestMagic.
Never mind, I found a math proof here

http://www.cs.ucf.edu/~reinhard/classes/cop3503/lectures/QuickSort01.pdf
cda is offline  
Digg this Post!Add Post to del.icio.usBookmark Post in TechnoratiFurl this Post!Google Bookmark this Post!Reddit!
Reply With Quote
Reply

« GRE CS Subject Exam with regards to my profile | phone result of subject test held on april 12 2008 »

Thread Tools Search this Thread
Search this Thread:

Advanced Search
Display Modes
Linear Mode Linear Mode

What you can do
You cannot post new threads
You cannot post replies
You cannot post attachments
You cannot edit your posts
vB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are On


All times are GMT. The time now is 02:45 AM.

Contact TestMagic   TestMagic Forums      Archive   Privacy Statement

TestMagic Locations   Legal   Privacy

SEO by vBSEO 3.2.0
Copyright © 2009 TestMagic
Ad Management by RedTyger

Scroll Up