Time complexity

Please support our Computer Science advertiser: Learn about neural networks and artificial intelligence.
Reply

Join Date: Nov 2006
Posts: 1
Reputation: SIAS87 is an unknown quantity at this point 
Solved Threads: 0
SIAS87 SIAS87 is offline Offline
Newbie Poster

Time complexity

 
0
  #1
Nov 27th, 2006
Hi, i was just wondering if someone could give me some guidance

i am working out the time complexity for quicksort and have got this far
worst -
T(N) = (n-1) + T(1) + T(n-1)
T(n) = (n-1) + (n-2) + T(1) + T(1) + T(n-2)

i no that T(1) = 1
so T(N) = (n-1) + (n-2) +1 + 1 +T(n-2)
but i have no idea here to go from there on!

best -
T(N) = (n-1) + T(n/2) +T(n/2)
T(N) = (n-1) + 2(n/2 -1) + T(N/4) + T(N/4)
T(n) = (n-1) + 2(n/2 -1) + 4(n/4 -1) + T(N/8) + T(N/8)
and once again i dnt no where to go after that

Any help would be greatly appriected
Thanks
Dan
Reply With Quote Quick reply to this message  
Reply

This thread is more than three months old.
Perhaps start a new thread instead?
Message:



Similar Threads
Other Threads in the Computer Science Forum


Views: 1610 | Replies: 0
Thread Tools Search this Thread



Tag cloud for Computer Science
About Us | Contact Us | Advertise | DaniWeb | Acceptable Use Policy | RSS Feed

©2003 - 2009 DaniWeb® LLC