944,126 Members | Top Members by Rank

Ad:
Nov 27th, 2006
0

Time complexity

Expand Post »
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
Similar Threads
Reputation Points: 10
Solved Threads: 0
Newbie Poster
SIAS87 is offline Offline
1 posts
since Nov 2006

This thread is more than three months old

No one has posted to this discussion for at least three months. Please let old threads die and do not reply to them unless you feel you have something new and valuable to contribute that absolutely must be added to make the discussion complete. Otherwise, please start a new thread in this forum instead.
Message:
Previous Thread in Computer Science Forum Timeline: Future computing technologies
Next Thread in Computer Science Forum Timeline: Windows script need help





About Us | Contact Us | Advertise | Acceptable Use Policy
Forum Index | Build Custom RSS Feed


Follow us on Twitter


© 2011 DaniWeb® LLC