| | |
Time complexity
Please support our Computer Science advertiser: Learn about neural networks and artificial intelligence.
![]() |
•
•
Join Date: Nov 2006
Posts: 1
Reputation:
Solved Threads: 0
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
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
- Time complexity of algorithm (Computer Science)
- calculate time complexity of the algorithm (Computer Science)
- Time Complexity Problem -Urgent (Computer Science)
- I hit a brick wall-- time complexity problem (Computer Science)
Other Threads in the Computer Science Forum
- Previous Thread: Future computing technologies
- Next Thread: Windows script need help
Views: 1610 | Replies: 0
| Thread Tools | Search this Thread |
Tag cloud for Computer Science
ai algorithm algorithms assignmenthelp assignments automata battery bigbrother binary bittorrent bizarre bletchleypark blogging bomb business clueless codebreaker compiler computer computerscience connect conversion csc data dataanalysis dataintepretation development dfa dissertation dissertationthesis dissertationtopic employment energy extensions foreclosure foreclosuresoftware fuel geeks givemetehcodez government graphics hardware history homeowners homework homeworkassignment homeworkhelp humor ibm idea ideas internet iphone ipod jobs kindle laser laws lazy linkbait lsmeans mainframes marketing mining mobileapplication msaccess nano netbeans news os p2p parser piracy piratebay principles programming rasterizer research sam-being-cute sas science security simulation software spoonfeeding spying sql sql-server stephenfry student supercomputer supercomputing sweden syntactic technology turing turingtest two'scompliment warehouse ww2





