Class Notes (810,031)
Computing (443)
CISC 121 (27)
Lecture

# 11.2.pdf

1 Page
120 Views

School
Queen's University
Department
Computing
Course
CISC 121
Professor
Robin W Dawes
Semester
Winter

Description
11.2 Thursday, March 28, 2013 8:52 AM Merge sort T(n)= c if n<= 2 t(n) = c+c*n+2T(n/2) Claim: T(n) in O(nlogn) T(n) <= c*nlogn Let c*=2*c PBI: Base ase: Let n=2 T(n)=c<=2c=c* IA: Assume T(n) <= C*nlogn for some specific value of n Consider T(2n) = c+c*2n+2T(2n/2) Show T(2n) <= C*(2n)log(2n) c(1+2n) + 2T(n) <= c*(2n)log(2n) 1<2n T(2n) <= C(2n+2n)+2T(n) <= c(2(2n)) + 2(c*nlogn) =c*2n + c*(2nlogn) =c*2n(1+logn) log2n = 1+logn c*2n(1+logn)= c*2nlog2n Using class structure to define our own data structure Linked list----(Abstract Data Types) ○ Only allow sequential access (have to go through previous terms to
More Less

Related notes for CISC 121

OR

Don't have an account?

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Join to view

OR

By registering, I agree to the Terms and Privacy Policies
Just a few more details

So we can recommend you notes for your school.