CS109A Notes for LectureAnalysis of Mergesort Input size n = length of list to be sorted; Tms(n) = running time of mergesort. 1. Call split on list of length n; takes O(n) time - Computational complexity theory - Document - PDFSEARCH.IO

First Page	Meta Content
	CS109A Notes for LectureAnalysis of Mergesort Input size n = length of list to be sorted; Tms(n) = running time of mergesort. 1. Call split on list of length n; takes O(n) time Add to Reading List Document Date: 2008-09-19 00:58:00 Open Document File Size: 59,62 KB Share Result on Facebook Company Guess / 2Tms (n=2) Guess-And-Check Solutions / / IndustryTerm Trial solution / exponential solution / / SocialTag Analysis of algorithms Arithmetic Mathematical notation Summation Recurrence relation Time complexity Computational complexity theory NP Merge sort Theoretical computer science

CS109A Notes for LectureAnalysis of Mergesort Input size n = length of list to be sorted; Tms(n) = running time of mergesort. 1. Call split on list of length n; takes O(n) timeAdd to Reading List