A sy m p to ti c C o m p le x it y

A sy m p to ti c C o m p le x it y

Running TimeRunning Time

R u n n in g T im e R u n n in g T im e R u n n in g T im e R u n n in g T im e

Input SizeInput Size

R un ni ng T im e R un ni ng T im e

R un ni ng T im e In p ut S iz e In p ut S iz e

R un ni ng T ime

• H o w d o y o u co un t th e ru nn in g t im e? – Ex : # o f ite ra ti o ns i n fo r lo o p , # o f ex ec ut io ns o f a lin e, # o f fu nc ti o n ca lls , e tc . • C he ck t he f o llo w in g e xa m p le s.

R u n n in g T im e R u n n in g T im e R u n n in g T im e R u n n in g T im e • C he ck t he f o llo w in g e xa m p le s.

sa m p le 1( A [ ], n) { k = n /2 ; re tu rn A [k ] ;

R un ni ng T ime re tu rn A [k ] ; }

Constant time regardless of nConstant time regardless of n

sa m p le 2( A [ ], n) { su m ← 0 ; fo r i ← 1 to n

R un ni ng T ime fo r i ← 1 to n su m ← s um + A [i] ; re tu rn su m ; }

Time proportional to nTime proportional to n

sa m p le 3( A [ ], n) { su m ← 0 ; fo r i ← 1 to n

R un ni ng T ime fo r i ← 1 to n fo r j ← 1 to n su m ← s um + A [i] *A [j ] ; re tu rn su m ; }

Time proportional to nTime proportional to n22

sample4(A[ ], n) { sum ← 0 ; fori← 1ton forj ← 1ton { k ← Max of n/2 elements randomly drawn

R un ni ng T ime

k ← Max of n/2 elements randomly drawn from A[1 ... n]; sum ← sum + k ; } returnsum ; }

Proportional to nProportional to n33

sam p le 5( A [ ], n) { su m ← 0 ; fo r i ← 1 to n fo r j ← i+ 1 to n

R un ni ng T ime fo r j ← i+ 1 to n su m ← s um + A [i] *A [j ] ; re tu rn su m ; }

Proportional to nProportional to n22

fac to ri al (n ) { if (n = 1) re tu rn 1 ; re tu rn n* fac to ri al (n -1 ) ;

R un ni ng T ime re tu rn n* fac to ri al (n -1 ) ; }

Proportional to nProportional to n

Re cu rr en ce a nd I nd uc ti ve T hi nk in g • Re cu rs iv e st ru ct ur e – A p ro b le m c o nt ai ns i ts s m al le r ve rs io n. – Ex 1 : fac to ri al – Ex 1 : fac to ri al

•N! = N×(N-1)!

– Ex 1 :

•a n= a n-1+ 2

Ex am p le o f Re cu rr en ce : M er g es o rt

mergeSort(A[ ], p, r) ▷Sort A[p ... r] { if(p < r) then{ q ← (p+q)/2;---①▷the center of p & q mergeSort(A, p, q);----②▷Sort the first mergeSort(A, q+1, r); ---③▷Sort the nextmergeSort(A, q+1, r); ---③▷Sort the next merge(A, p, q, r);---④▷Merge } } merge(A[ ], p, q, r) { sort the two arrays A[p ... q] and A[q+1 ... r] merge the two into one array A[p ... r] }

mergeSort(A[ ], p, r) ▷Sort A[p ... r] { if(p < r) then{ q ← (p+q)/2;---①▷the center of p & q mergeSort(A, p, q);----②▷Sort the first mergeSort(A, q+1, r); ---③▷Sort the nextmergeSort(A, q+1, r); ---③▷Sort the next merge(A, p, q, r);---④▷Merge } }

② , , ③ - Re cu rs io n

① , ④ - O ve rh ead

D iv er se A p p lic at io ns o f A lg o ri th m s • C ar n av ig at io n • Sc he d ul in g

–TSP, Vehicle Routing, Job Task, …

• H um an G en o m e Pr o je ct

–Matching, Phylogenetictree, functional analyses, …–Matching, Phylogenetictree, functional analyses, …

• Se ar ch an d R et ri ev al

–Database, Web pages, …

• Re so ur ce A llo cat io n • Se m ic o nd uc to r D es ig n

–Partitioning, placement, routing, …

• …

W hy d o w e an al yz e al g o ri th m s? • A ss ur e th e in te g ri ty • M ea su re t he e ff ic ie nc y in r es o ur ce m an ag em en t m an ag em en t – Re so ur ce

•Time •Memory, Communication Bandwidth, …

A lg o ri th m A na ly si s • Sm al l in p ut ? – Th e al g o ri th m d o es n’ t hav e to b e ef fic ie nt • Bi g i np ut ? • Bi g i np ut ? – Ef fic ie nc y m at te rs ! – In ef fic ie nt al g o ri th m c an b e fat al • A sy m p to ti c an al ys is d ea ls t he c as e w it h b ig in p ut s.

A sy m p to ti c A na ly si s • A na ly si s o n a b ig i np ut • Ex am p le o f A sy m p to ti c N o ta ti o n • Ex am p le o f A sy m p to ti c N o ta ti o n • Ο , Ω , Θ , ω , ο no ta ti o ns

limlimf(n)f(n) nn→→∞∞

A sy m p to ti c N o ta ti o ns • O ( f ( n ) )

–A function increases at most at the rate of f(n) –e.g., O(n), O(nlogn), O(n2 ), O(2n ), …

• Fo rm al d ef in it io n • Fo rm al d ef in it io n

–O( f(n) ) = {g(n) | ∃c > 0, n 0≥ 0 s.t.∀n≥n 0, cf(n) ≥g(n) } –Conventionally, we writeg(n) ∈O(f(n))asg(n) =O(f(n))

• In tu it iv e m ean in g

–g(n) =O(f(n)) ⇒gdoes not increase faster thanf –Ignore the constant ratios

• Ex am p le , O ( n

2

) – 3 n

2

+ 2 n – 7 n

2

– 10 0 n n lo g n + 5 n

A sy m p to ti c N o ta ti o ns – n lo g n + 5 n – 3n • A s ti g ht a s p o ss ib le – W he n n lo g n + 5 n = O ( n lo g n ), w e d o n’ t hav e to w ri te as O ( n

2

) – If no t ti g ht , w e lo se i nf o rm at io n

• Ω ( f ( n ) )

–A function increases at least at the rate off(n) –Symmetric toO( f(n) )

A sy m p to ti c N o ta ti o ns

–Symmetric toO( f(n) )

• Fo rm al d ef in it io n

–Ω(f(n)) = {g(n) | ∃c > 0, n 0≥ 0 s.t.∀n≥n 0, cf(n)≤g(n) }

• In tu it iv e m ean in g

–g(n) =Ω(f(n)) ⇒gdoes not increase slower thanf

• Θ ( f ( n ) )

–An increasingfunction at the rate off(n)

• Fo rm al d ef in it io n

A sy m p to ti c N o ta ti o ns • Fo rm al d ef in it io n

–Θ( f(n) ) =O( f(n) ) ∩Ω( f(n) )

• In tu it iv e m ean in g

–g(n) =Θ(f(n)) ⇒gincreases as much asf

• O ( f ( n ) ) – Ti g ht or lo o se up p er b o un d

In tu it iv e M ea ni ng s – Ti g ht or lo o se up p er b o un d • Ω ( f ( n ) ) – Ti g ht or lo o se lo w er b o un d • Θ ( f ( n ) ) – Ti g ht b o un d

Ex am p le s of A sy m p to ti c C o m p le xi ty • Ti m e co m p le xi ti es o f So rt in g A lg o ri th m s – Se le ct io n So rt Θ ( n ) • Θ ( n

2

) – H ea p S o rt • O ( n lo g n ) – Q ui ck S o rt • O ( n

2

) • A ve rag e Θ ( n lo g n )

Ty p es o f C o m p le xi ty A na ly si s • W o rs t- ca se – A nal ys is f o r th e w o rs t- cas e in p ut (s ) • A ve ra g e- ca se • A ve ra g e- ca se – A nal ys is f o r al l in p ut s – M o re d iff ic ul t to an al yz e • Be st -c as e – A nal ys is f o r th e b es t- cas e in p ut (s ) – N o t us ef ul !

C o m p le xi ty i n St o ri ng /S ea rc h • A rr ay

–O(n)

• Bi nar y se ar ch t re es

–Worst caseΘ(n) –AverageΘ(logn)–AverageΘ(logn)

• Bal an ce d b in ar y se ar ch t re es

–Worst caseΘ(logn)

• B- tr ee s

–Worst caseΘ(logn)

• H as h tab le

–AverageΘ(1)

Fi nd a n el em en t in a n ar ra y of s iz e n • Se q ue nt ia l se ar ch – W he n th e el em en ts ar e ran d o m ly d is tr ib ut ed : – W o rs t cas e: Θ ( n ) A ve rag e cas e: Θ ( n ) – A ve rag e cas e: Θ ( n ) • Bi na ry s ea rc h – W he n th e ar ray i s so rt ed : – W o rs t cas e: Θ (lo g n ) – A ve rag e cas e: Θ (lo g n )