Class Notes (808,754)
CS 234 (31)
Lecture

# notes07a.pdf

2 Pages
77 Views

School
University of Waterloo
Department
Computer Science
Course
CS 234
Professor
Robert Sproule
Semester
Summer

Description
CS234:Lecture7 May-28-13 11:33 AM C2*f(n) Complexity Analysis T(n) Lasttime: ○ Evaluating complexity ○ Big-O,Big-omega,Big-theta C1*f(n) ○ Common complexity classes T(n)istheta(f(n))iffT(n)isomega(f(n))andT(n)isO(f(n)) 0<= c1*f(n)<= T(n)<= c2*f(n)for n>=m Example T(n)= 1/2 *n^3 exponential f(n)=n^3 Omega(n^3) O(n^3) Therefore,T(n)istheta(n^3) PropertiesofBig-O Sum P(f(n)+g(n))isO(max(f(n),g(n))) Ex.f(n)=n^3,g(n)=nlogn O(n^2+nlogn)=O(n^3) Multiplicationbyconstant c*f(n)isO(f(n))forallc?0 Ex.(85/c)*(n^2/f(n))isO(n2) Product O(f(n)*g(n))isO(f(n))*O(g(n)) Ex.f(n)=n+logn+5,g(n)=nlogn+7 O(f(n)*g(n))=O(n^2logn) Polynomial n^kisO(n^p)for allp>=k Ex.n^3is O(n^3),O(n^4),O(n^5) Logarithm Log(basea)nisO(log(baseb)n)foralla,b>=2 Log(baseb)n=[log(basea)n/log(baseb)n] Listof operationsin Python Best Worst Comment case case L=[] O(1) O(1) Constanttime L=[i] O(1) O(1) Len(L) O(1) O(1) L+L O(n) O(n) Gothroughboth lists L[1:] O(n) O(n) Copyingentirelist.Elementbyelement Range(n) O(n) O(n) Creatingalist L.append(x) O(1) O(n) Bestcase:assumingthereisspaceinthelistto append Worstcase:haveto copy theentirelist L.insert(i,x)O(1) O(n) Dependshowfaronehasto go to getthere L.extend(L2) O(n) O(n) 2lists,saybothare sizen,wewantL and L2 to bejoinedtogether. AllelementsofL2areare copied.Ifthearray needstobeextended, numberofstepsbecomes2n,butintermsof big-O,it'sstillO(n) Sum=0 ForvalueinL: Sum=sum+value O(n)=>theta(n) Listcreation L=[]->O(1) L1=list() ->O(1) L2=[None]*n • • • •
More Less

Related notes for CS 234

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.