eee ga a | £ ALGORITHM = x Topics | Schedule WO Dboducton to Algor ithra © Analysis of Algaxithra —Necd for Analysis -Methadology oF Analysis — Types of Analysis ~ Behavior oF Algorithm @ Asymptotic notations ~ ee a . = definition 5 — Propettes — Patblem Solving @ resign Stetegies - @— Divide & Conquer” Q- Greedy method @ — dynumic Progrermming — OVE diffiait © Gap Techniques - ko comected , Stangly cormected Gi-Cannected Cornponertts @ weaps & Heap Algoxrtmns With = Applicertin ts : ag Complerity “Ineory = PNP, NP- Herd, NP- Complete a Terk Boots + © Pendementals of Algaritr — (layne & sahomi ~ Goad for beginner cnaw) @ Vraduction +o Algorithm ~ Cormerr U Advance a) Algor besign ~ “| crmetssia Aga. A™ * Drboductim . formal. % Algorithm - Chern) consist of Staite, set of sleps to solve a given paoblern Ccompeles) L step | stekenent — onelrnove hinderntitcy Opexe tions X z= xty | 7 bon ers ex Kea XY Cevery oper ' 7 ’ t to Pope 2 veddca} satisty to oper) pefimiteness Clea] uadmbios ions ) > Effective Compt take finite 44m +0 complete) B, Algo. “may accept 2¢0 YF rnare — i/PS. > Prduce uttecist one 0/P sare) 2 Desired aa (Pr C ) ¥ Life Cycle i- © Problem Definition @ Requirements [Constraints [ conditions] ey Sovting.- - , Condi. 4 Lan) = (a £ Go ORL -- © Design shutegy [ development of Logic] @ Express the Stacrtegy CAlyo. | Flowchart d lidatim= @ wlidetion- ‘to chect/ Prove the correctness oF. Algo.- — whether meet ctll the aequivements Boe & Amalysis Peapennming Lem @ ttmplementaton Ceselectin oF) Pts, 0.5.) resting umd Debuygin)- ; o Tem Debuiygiy” . cto identity omtine hidden exnors B testing “in SEPy Need for Ancilysis > (whit ) Rmplerity | > Resonce Consumption andl, Due, egis tee) Bandwidth j Batteay Pong (rw) Cpawer cia a _. p Ie fag > Pexformunce Campurism Mabie problem cet ficient) (Ta ‘end best aang all) (Aloo) ai At, AB i A x Methodology of Analysis Ctow? ) Hw Platfar - (Archi. + Devices) 7a < Ga bs9 erent Nsw Papi 10.0) Ct O Apos-teriori Analysis [testing ; : ( Expexrmenteton) Adter Tenplementation” K Adve. Eycart valve e9.C2-sms, 515) K Dawbuck~ Ditficvlt Crime. consumption) > Nonamiform vA [° change platfem & ler than ry by TE becorres difficult csms) cen) to mate Perfarmneince - Compenion aes @ “Independent oF Auch Pab rm = CA Paori Analysis) E =v D 2 ee go. 071 PPE:A Dactte! .) ¥ Fetomerte | Appaoxrerate value fy Chndependent af vmnit) Crypt ra 506 5,78) ie e 4 Adver ~ Uniform Arvitlycis ( sufficient enaigh +o make Pexborncnnre caenpaai son) LX ([Iprion Analysis » peleamimatioan ot asder_ Of Clarlement { constouet | p. ¢. Oper tia Cota ctouctuye) No. af mes [ frequens re of pundament all oper’ invalved iva tre teste rent coer) 4 ») LION 5 x Algoxithan Test ae bic; § flee for je 2 coe nTime a ee peal eee oT ow) my: for jor” 4 nr \ for j= 110” } | mH VAR ¥ t(M= taney? \ es a 0(fcn)) = OC) -Gubyf) 2a. cycle.—l029 ' we cam ignore the Bike = go-Lleakn \ price of cscley beac Cu ~ 10 = 15 lakh Oca) cod pore to plane.) plemne - cave f fe As il) Fo) is oc).] sat ee sy) foe | — 10) - break; ac |ey, Ux Apion Analyis &, Asymplotic Notations ~ = _5 The Basic Objective of Apdo Analysis ist * cisociale mathematical fmclion (cn) repre. coring lime of dlgoxithm as a Aincuim of 1 ye site n. Crerte oF growth) ; jo fn) is determined by applyin-» mM every Stcp oF statemen: Opes tion of the Algarithn, > the fimct ardey of magnitide or Data Souctuye : 5 Asymptotic Notctions erve forma) NoterLins for? deserting wite oF growth af the time ak the > algorithm cmd vepreserting the behaviata” oF the ulgo. tov fixed ,i/p. size: d 5 ¢ W fen) — Time Complexity Cinpute size) a fh (MOCO ois Crete oF goth) Cfncaee oe “nme > |Méar r. _imeveasef > comtant CO ( Asmptstic) = Polynomial Cn*) Nok.---- . > Wogazithm (09) os we at = Eyponential Ca) cas tre] tne prob a 2, ; K/ ( di Fixed I/p size = Behuviaws C-type ot Analysis) ? t ¢ — Quick Soe = n-elements m=50 Ce A of 9.1 C141 3 ay | dea) ; )3 (Ne Classes ™ sa panel — Perry ‘ ula ley wee, guar) MIN rnc.|ee, — Chacvement /pecyene wnt han og1 Behuviate of Algorithm | Types of Algorithm’. - VAlgantheon aves different times for ditt. ye Clatcer or dif, Uyrerngement of i/ps Of -fixecl size -» the Algorithen behaves im 3 diff cuses for \ cite Wp classes VW Worst Case Behaviers= Won) te ee ie the Algo cloes nay wom ond hente takes max, €me Ww Best Case Bchaviors/ Analysis = Bo) Lyeheas ta the. ip class ter which Me ae dues rata wow ernd hence takes “yi ° : ‘ ‘tig Avesige Cause Behaviaty> Aco) = Probubility «nat the Alga \ Le: takes ip fom thert, clas, cheps tS teps S a ig eu ASO) Mode ag Bim t2 3 pb — 0) Pr PR Pa ¥ Mwy cuse finalysis difficwkt to cory oft drong 3 as ib Mvdlver 2 s-kepr . () Vividing the ips ia che diff classes which the | » etlgo. pnay dake (tity ta, -- Te Cas 9) Velewenmne the time for cach iye class, CM Ut rly, rte) O Velesmme the paobabilitd that he Algo. terke the Wp -Gorn the corsespordy — fp Class, 1) (EO Py Pale, oP | Pole ) : g_— — | athe avedge time of the eilyantnm if giun by re Am)= LY @xti i= Fen < Ac) < Wen)| Possible i ——$_— we 2D BM) =AM) = Wm) — Alga 2 27 Bn) =Am™m) L wm) e 3? Br) Am) 2 Wm) ay BM) € Ac) = Wom) % Asymptotic Notations = > Asymplotic notations cre. fasmal mathematic matutins for wepresenting -the bounds of 4ne fmctions ie lower bound 3 Uppex bound and tight bamd. — Sice the time of the Algo. is alo vepresented Us a mathematical ametion in Apri cmalysis, Asimptotic Notes cre -> Cpplied for “representing the bounds on the time complexities OF -the crlgo.- = Asymptotic Notation ave classified int 2 ypes O Big Notations Be © Smatt or Little potatos ee _ D- gf ¢ar ¥L ASMIOTLIC NOTATLONS © v Cas ne) > Let fen, gon) be Furetions from | th \ PT set of te ae 10.O Big. oh (0) - Upper Baimd Of a AnctioN = fm 1s OCI) iff gn) | | wheever 1>k and for same © >0; 9 ge teren® 6 vtentint | . fom © 3n% | ee Ge see eee gon= vt : -£imé OCI). a 5 fon) = Or?) — 2OCr3) 0004) mentens (nk) 3 fen is alfa lets enan 13,7" but we have fo choose Closest value ta_wppex” bor x why! ex twunt to puschare~ plot- ™y esti tory fs yotath @ us lak « 2S _ a5t puilder — Estimesrte Price © too lakhs, bit pe shoud give cbsert value to eséimeation nd Builder elle estimetion’ will vot be greater than yr lakh, = Te oe qn this is clorest Estimeton f os¥ A | ( @ By Omega (A) ~ lower Bomrd 2 a Amctign > £m is (gm) iff [fon) > ce gen) whenever’ v1>k 5 for some <0 ; a £m) = amen? (tom) = acl) am am) + =A) : el) ; = iM) “fond is ant) | DO Theta (6): Tight Bond". | > 4m) if OC gon) eA { /. = iff #en) is Ocgem)) AZ & fom is acm) Lox Y , Oc) to FON) = Lang ; Se CFE). fe OOM. x(n) ex ee! fm=n) If san Ca hin) oe m5 NEE NOM Ong. Leet iy : NY ea BRR. M1 IS Onn) 7 i can. 7 ee i, O(n) nem fog m1 is OC % Lon) & fm) = glee iS onx Dominance Relatim , ' Qn ch hon ond nedon enon? LENLU LM % 2 Type of Question * WM £m) —% 0,2,O0- very wire ai) 2 | move function Ex «{m=amym » IM) = Logon 2 acm is Of) @ tin) is a (go). ex femean® genpe2” <. £m) is OCom) , 1>4 @ fim =r; 9c) = 40971 tak los > ch both sido = LOIN 2 My 1090 2 fay 97 2 gen) is 0 C#m) 4@ tome L0rn genre neon) | al fag Choon"? rate tag teat cide wi, Logen fog A090, 9—/g—-409n fy porn > 9 tog dag =, PS ‘ 2 gc) is O (fem) “107 HtCo ibeceoaie ce oY which of the follwing care valid oF viel? Var boon an = Qo) qu ¢3) ly 1f AOCxXLY they n% is OCW) - Le oo) | : 2 is OC) 2 —? qt 2 sm c a” Qa i Ocu) =x chau Omni” i¢ on™ - bym™ Wve Coes, : 7 3, m=2 (n43 owe en+g - OMY ew LOR) ; 5 mek” js OCn™, © gm) =n -~; 0¢ng too =73 _ i =n 3) > loo “~ Hin) =F =| OLME 10/099. > 10,000 \ =< vt 2% it 2 i > Sn) = 12 B Nz 100 ; “a £10,092 s Kin) =n? , m>look NE 10,900 = r. gday is OCkOM) BR geo ts 0C9¢n). ; Sim) if OCI) = . ; ue i » 1 > 10)00 : Sem) = ) MI> ley doa. i ‘ Hen) © I( CM) aon) C91. FE OY TF Blom) Is OY TF Blom) oe Che $00) nga ¥note- “The bamds provided by big noteatims may oy muy rot be cisym ptotically ight brt the bods provided by little csmeill) atertions is crluays nak cisymptotically Fight. x SMALL] LI TILE NOTATIONS - oy Small -~Oh ©) - fon) is acgen)) fF Fen) “@_ gen) whenever 7>k for all © 29; fs | Oo a £MN) =v ocr) 5? Small Omega Cw) - => fm) is wg) FE FCN) > C- gen). uheniever Tk; ~ for dll .¢ 79; ae e9 Fe ah . oo wim) ‘a 3 on X Anclooy bly Asrplatic terians & Pec! Mrmbers= > Lek cp? &%g be functions ;° ’ : : er 2 6 be jac ms, D fon) is OCKm) Eo 4Lb 2 fon) is CIM) EY aZB 3) ‘fen) i OCSM) ey Ueb uy fon) fs ocgm) gy ueb sy €o) is WW) ey arb re : aj ~Pripaties of Asymptotic — nolating~ (pisoete Properiny UY Reflexive Property L tiny = OCfen) -v fom = (fom) : fon = @ (fm) ' C -x b> Symmetric Poapaty 409 is 6 Cem) => IC) is Ol fe) o> Teemisitive Property ;- £eM = Olsen) g gen) B=OCr =) Fen) = Oho) L a oe gn at ne. i E Er c dy Teemnspose Symmetary — se feud is OCocm) | then| i€¢. gen) is anlfod). TF Fed is 0 Cee)’ ther TIFFS ICO is w (Fe): a ©) Teichotorny — Property - of te fol lowing mst hold : alb)e —r his ¥ Node + — trichotovn? Property is. Mot Setistiel AsymptoHe Notations » a@ men igunliy 14 SPX Cotes \ : no ae la Harsh ipx Gevieral Properties :- ch Feo) 8 OC gem) i thn afin) is OC9m) )3 ayo Ou rv is OC 9 Jy FO, x x (109 N) ; ww SD wyn fs CC ), soy @ Gaye : wm io fe 1S OCa" ) . xx0,K5, | 9 x=4, Get nt c2” my) 5 tf £m) is O€9em) & dem is Oem) they a> £m) + dem) is 0 Cran. (900, eM br tom - den) is “OG 9m) ec)? 4 se Fon) = = gent) e den 2 B= 0 3) FO) 490 = 4 2 = O(n3) ££OM 90M) = vi nBei nS = Ons) ent Asrvurge the following Aynctions iv? the ineweasin) oder, of eRe =f) FIM) = 27 — expo 5 aa x 2M) arr — Poly a7 [FL CON CFU how F360) =1.L09N—_ Paly 05° Mie fyu(m =n — expo. « . v Taken = [eo 4 bg CHM) = wnkog? tov tor WD 409 (mM) <= 3h doyn eee fv 6cndama) « ir +4 foj fog) ‘ 24 tty 40) (mPHN) = fon doy = « ayn) mr gyFh? Avrange following Kections in Trrsecsing : E a © Gop)" © va!ly4 Log? eA AV*hoon £797 me-134 975 3 hy tog) vt 3; j ‘ » 409m IyNLO9N or 12 Jaap | on!as Loy 5 Clog)? liy Ya toom) 129 13 ve a s Ih I Mogae ee 00 ta Me 247 Gay" asy 2 1) 11 aM. pe : x Gy: : : ' i xt Determine for eich ‘ hemes Fen) 1S 0 Caen) @. gem is. O Cem). fon) gen) by ee S : > 2 atm, 6M = 9m) = OC Fen)? ii 4 - oi by N4 Loon nin = = ; Lene © 3q ta Cnr : ny = OCs) 3) n+ em nt 9 teny <0 Cron)” tog(n+ emi) & 2409” aN 2 up vrkom . vie 7 4) =O Caen) on l . Cogn om+i) 4 % 3 Crssny 6> tas ) A ION =O Cen), " © ‘Yu mom4n vy ukomtt Coom-t > £1).=O¢ se)Y D-azfidar ex? which of the follawing Is ove or (alse? > ar ffoon O(09 409 M) ~ ralse (7° % losdorn 5 yoy 409509) by ot #¢ O (nk) - trie (> mae 7 1 poly) cy i = Oo) = Fale Co A? 40 100) _ ae Si . ne © d; LOIN = on) or todo € 409 B+ fm) = 2 Om) is Oo) ~ rch _"* ” 3] ye — @ 4 iS Logi if OQ ndosm) = é 7 zeim 4og 1 + Lojr 440024 Togn f=] = hog ([-2-3 1) =tog(nt) Tow, Nhe ncn) Ce) te 6 vw am en mits OGM) ~ © fr ko lrto%n Of bkerby ‘ i ; . VOY for “Kia 1 OY) Gen) On?) § -(0) . ‘3 eee jAy ae® gen & wen) wepwesent the avenge cate ane worst cuse .complerity of Algo then unin of the following is alway tet a7 CO AG). is (itn)) by Aon is 0 Cure) So Ac) is Otuem) : qd? fem - if. of wtv)) 2 _ ‘ Exe Tho packages CAlgusttrrs) AeE ave cwilable for pacessing 4 database having lok records Pacvage A -sequires g.a09ln" lene vunits while fucage 8 sequiwes so-n.sogn tine sumits, to proes mm yecods. what ts apo" crnallest value of a E L fer viicn package & is peckcred over parkeue A a7? b7 lo } M76 dys eee) Oe ee, m= 10° Acme 0.0001 X10)" = astride = 10° Ben) = toyt® tog WS = 6 An): > 7 = 50 > Ac) “not — paekesed © Nou veg, n= 108 Aem = 0.00014 Wd). = 10 °K? = 0% em =. tox1os Pe A Bon J09 1 = 6x0 & Aca) Bem is pyrefevel. -aver- Acn)x3 Let fen), ge) and hen} be Kenctions sven that SS tm) is Olam), gon) is rot Oto), gon) 16 OChon) x him is Coo), Which of the following statement is false9 i: 7 cp fn) thin) is O Cam) +hen)) be Chm) o hin) if mt OCF) ud fin hom) is: not OC 9m). hen) — tomy gm =n) u nr nr € Recursive Algoxithm DO Algorithm what ) 5 1 if mel) then call AO} else £ what nl 5 call Bo) 5 j oa: 4 ‘ ; i A 27 OC) 7 3h Bo”) — On) : > Skep-1- Derive the Math Recarsive Famction = , nel n>] 2 Tm) = € =f+ TOM) + Step-- > Back Subsl-ion times 14 Tal) ty —O@D en i Gicns TH0+ Yrrt ‘ eee “TMNM= TOs es Yt C141) @+ Ct4l41) {oa foal a td! h. mn 47 ae cae Nt? a cant Io yc! a] can 40409); Lon) = tnd + 409% | ~ dog =) G ae Of Reansunce after Eliminato7 Now, ntlagn Is O(n) as wellar n+sapn. is, a CN) PA lgorthmn Am) £ 1£(n£2) wee Ga) | else vetramn( AGH) ) Yo 7 OD TM = ¢ ne ' £2 = 141M), nye TOM = t+ TOnk) tinh) 2 141 cra) i ton = wht dren) iG Tike. Rent =0u€ testems ieieee One) to = ea Ont) . g ; OF mow, (el Y= 24 tonya (7 ay \ IK = Tt (28 jak ~@ L=bgn Loos : Ce ft ns 2ipges TENE Y= be take | 600 Br E gee TA) = C+ Lay Joya : = Olin tant) vdeo 1 TON =O (leg al v= Log A = hoy (Loge) ; HO toms ¢ Pale i) i et Cie eee teh aay es tony = re 2 TOM) —O : ui S y 2 renee tO") © spon 2h + 2 C+ eta) «Tas 142+ 4 cole) a ee | i . Tage et et ait 2.7 (n'9)) Poe nto) ye Loon. [ToS OChog 1) ] ABO = et * geen toss z | [Ee hogm @ mt — Pecursive Cimtn) £ a if (met) : oO > Yetm cD, .° g “ else oe ® BCEANC seunsive(n1) 4 Yeowsivemn-17) « ‘| ? = tM = C »nLy = 14 21(n-1) yyytm) = [4 2 7m tat) - l-4 2 (42 1H) ~ (4 24 YU mt (md) = (ft 271u (T4271 (n-2)) = (l27eu ae rcm.3) = erg. gel a ok. tn-k) low Bly ok 4(m-k) tt Mr f=o mow), m-bk=!l wtren-l ' nt: - at 2 rc) i20 nV = 14 ai nl 4 (Se ae cae m2 —| ie a eae) a Mee we ag ttc, Mae nl =7- 472ee nel / H Tne C vf) Oy y>l 1 1 = 14 To) \ 14 ton-l) Fi) = re 7-2) = i+ = 24 rm) : 24 p4rcn-3) Ton) = 94 T(n-3) Tin) = b+ TO) mOv) Y= 4 ken-1 - TM) =n-l ¢ TC) Ro =nt4¢ | Ps TMS ce | ney Ete nsl) wad S)-s a > TM = Tem) ander = Tm) +e > = tTNV4 M1) 4” = 11-3) 47-2) 4-1) in a = mE-04 M4) |, = ws) vc Cs© Algo Am) if(mé7) yetnn G) j else 7 vebton ( Amin); ae ee Gl) fd eae =l4tmi+n , 17% TO) =7@)in © ton) = TOM"4) + Gr) en 2 tenes 4D 4H _ VK) o @oR) 4 ai- = (12 ) op G4 -- 4(n-k) 4 woe (4 Gk) sk Ge Tone: TOM Aa GA = TOM EATEN VG Sy 02 z¢m = TOM) HH Hy Ys . een y ma mle rate = io nei Koh tn?) voPX Promamr — Saymerle * $700) ty Co te 4 low , orn) y Ot yy for je a ton 4 Foy Je 1. (07) —» Ow) $3 W for ie 4 tom, oe imdere Heve MYO, for je 2 to Nz = O(n3) eel G ae eL far VE 1 to My but YyeCate So 100) Wy jr 4 . HUH -- 7 while Cj en) sehen Ke; akon 2 MamH , . sue Ly Oy) . 2 : O (69 n) (%, 997 for(int; i6=N; 441) -OM) : . kogn faye} Fon; Je 5x2) O(tosn) Cn tagr) a - jeolin k 67 fey bel a vile b £ ”) L 2 3 3 6 { 2 Hy 3 ee 0 ( 4 s 5 \ veka, < 6 za j i . a —7 C141434 Beh) oe vc) 1 6 ( - Hit4. 45> ) JOHN) yn \ 5 >ot s is OCD. for (j= a 5 kIT oN1 4 tH) $5 SS) im | 6) xi ”M ' * 2 OCM) itm i~ i ‘ & ex camter = tr [101 Cc : if ( At== 3) COunkest +, else 7 £ccounter); comkey =O; 3 . ¥ Givn= FO is. OC). —Aci...w) if Gd Binda tracy > 4 dittesent cuses W) A CI=4, for [=1 0" om) GQ aces 24 Om 5 Ot . alt wh. » + Gi) acdel 1 for # my, (Mais 4 Gals) FOCI) Cee Tyyrsee CW: pride 1, ™m-1) (m4) 4 Ca) 44 (0m | i*X Assigmanent ~ An aaaay vlement in.an aad MW 7 is called ct leedey if ik 1S gaccrtey than alt elements to {he yignt of it ia the array X “Che besk Algo. -to find all leldrs (1 an any GQ Solve Ke in OC) Lime 2: " » — Oneogn) times .. " OC) times dy on Tincene tiene ving vight Go let Par p-as[¢laz : 7 2 4 Ss ‘ a LD,rDLrmrmrmr—~—~S~ms— = Ee : A Algovithm LEADER c a max €— Xt) 5 + ' 2 for 1 (n-1) dom 2 1-2 t eae we lf (xtiJ pmax) ; £ pome (xc); © cs muy =%CII; 2 3 3 4 ‘ *K Basics - Fundamentals. Always Remember —~ £m: go) 2 tony is OCgem) — it doer not mean fen) & gen) eilivays, fm) 6 690) , N>k ¢ | t 1 > 10/000 - tow, Leis cho Om Type tj 9@ fenr= 21°? gem = toa T® ACM, wy, _—— ; —> Smalley tRmelions ave im oder 4 a0 £ Olsen) [P20 Fer Knee > 2! is OC hog 1) m > = Csome values) O Fone! 5 Hen i: h tom is Olsen), >? Ka 7!2 3Ce eg te to fy je jton a : nen n4+on-2- 1] aa) om is Oc). yA! for | — 4 ton? I . ] Gon eae es cod fo k oH 2 tod > 7 jet j CmM= > a = a ie | j= i41 k 2 Lie = nena) com) fer ‘ a pee — nicntD fet & % = Cat Ja nemencenes) i=0 3 a F 5? = fi =I [in LD met of oe Ss a 3d ied aa ee ‘ OLjen “ oa z ilo pa. a jap 1D = ar) at : ¢ ™ ne Saad 214) 2 ee 2 2? | | = Jente ven, y & why odd pi? il =m eis even =O.) om is odd © % Bionamial Grefeicient x Cn o mo 2 MG, Y : ' M=0i. t \ alog b a Loy x 3 Log _ 49,7 Loo a b tog x L b = iq tay. x foi b b ee fP aay, art, ay. --- av” atare ars ar —- +07 n, - ari) sume EET 7) Cre) , ate) Bene ci-m) AP? a, ctl, etre, ate Sum mters = % Cra denied\ Ext £( integer 1) Yo ifm = ') eran 1) else £0); #Mh)) , 4 = © (on) f > 7) = © sa a = 1+ 27%) a ah tin) = 2 TM)+1 — @ ower gem 2 2. ( 2-1) +1) + gen =u. Ty) +? 41 a) Gt) al aa ott 2h T048) + F,* epee pene (Met) + & i=0 al mov) Tee i grace +8 2! caf ce ih aaa eeHe aah | ' is ( = 2-2 oe) edn - tft i oe es d iy a -constenl - tTm)= OM) , n>2 tus j= 25 while (joy) { jen; avez!) | while (379) Logn Loon yn . 5 =. t ter C jeans \ logn RAT ene) 5 inne”) = Gon? 4 | p= Kt 7 { | | | Psoperues - O re fen) is 0 Caen) then K | (oe k | f O( go) |O af fn) = 0 C9cn)) a nn) =OC Fm) ioe OCU iX SPACE COMPLETES > the space Complexity of a paablem P denaled as sce) = C4 Sp here C- conslemt Spice Sp- ‘Instemnce Chepeiclaistic * Conclemt Space > Cc) —> Tt remerents the space fos StI anstuctim te the code phy the space tor simple vervigbles cmd dertastrictives thet Lyllotwe Stertic Memory Allocation & whose sites ce fixed & knoun im advance. t > This campment is geneully conrtart value which i Qc) ; KoEastance = Chere! CLEMSHES Tastance Chavercsev— = This campanent wepweserts spuce tor varicibles @ dynamic deter strwicboes, clagrigerte variables whase size is Nok known Cc priori but msternce of the problem being ¢ q depends on the colved 5 Te also includes Space fer Recursion Steak eS Pyocechve Ape Cre yb ce) f yehim Gebtc)j j : Y f E 4 enS Ga ce G48 Se G yuy =3 | =0C1),Est — Paoceduve sum (Ayn) t int in,sum=4; fo jo Loy gum = sum 4 ATID) yer Csim)) j > $S€sim) +s = C+Se c= 43-4 Span d-constemt $Coum)= dtY =O0M™) 6&3 Pyocedtwe Rsv (4,7) f itcn=4) | eto (G); else wesemt AO + en (4,711) 3 | _ | garm of lll the elements of cneuy Spans stack ob lenh [ racers awe” : S creck gt Cn! - Words Dy age mp words Sp= mn = own), x0 pyocedwe MATPIK can) £ integer AT! bn), PD ER See 9 OC) jo, ey ) ee athdel Space + om) Ge ie Ge 2-simensimal crevay) | Csite of woes - We don bother vo. of eras - we bother)1 DIVIDE & CoONguEL x Carbo! = Abshaction os) a camplex 29 When problem) became lvoe \ 9 idhat should become lenge? > tp is serid to be srmcill Gor eazy)? A poable m oper to ie i DS solved iv) 1 ow 2 S Otherwise — lenge it is Shmilay la Divide & Rule x Histaical = Backgraind* one of the war, Nepolec applied this seutegy size of Oppanene crmy Is layer. ste divided his camy mM 3 parts, ¢ enter middle if of Oppo auny ¢ wor the War medPtl Vx conbaal Aboseerc bint * am mel — Procedute DANDGO 4,e,4 1) if : ah Sma (p)9) then year C09); ele f m < DIVLDE C?,1) Si &—DANDC CA, pym,%) $2 E= DANCE (A, ma, T)12) cpetsrn ( COMBINE (51,52) )j ane > SMALL, DEVIDE , OMBENE = App hecrtiat Dependence.x Timing Complexity - > (ek TM) vepresents the Timing complexity. Of Procedure = DANDECN); TON) = gen) — Cmast of Lhe time costar) - (is sare hese gom is aceceq) = 2-10m)4 fon) , : fem Is 4ve | | | ersese Pe Emding Max. 2g min . | (MAK -MEN Pasplem). - Bence | g O-6 3 IS zs 30) Ae lf weak TY ymax — MIN — Aa). ae ee eo C Mdox, Compton) * k £ og catpmex) | MaKe acid 5 ae CElemene ae | ic caci) 2mm) C (es a i min ea CD) > total ne. of comparisons = 2-1) Sree Oo a 7 CG¥ NM DE ( Divide & Cpr) OM) ‘ ay Worl cule ° SY Dermecunygy No. ol Comp: 2 (n-t) 2 Best Cue: > Imacaing No. of Grpa > (1-1) War AW. Case D- 23i¢laz yon ca cy cs) ed oH Gy 12% -19 6 QO td WE 29 I6 I STRATT - MAXMIN = a MAX —— min <— ATII,; 2@ fr jo2twn é t T£C4tD>™axX) then PD omax — Acid; { if (at min) } min — Ati; 3. yeturm Cmax,min) % Intexested> Total mo. of element com peniso cD Best case — tracrearmy i o> n-1 ii) Worst case pecyects ing > 2cn-1) Chi Average Ger on ey W9. Fias€ comperricoy or com C35). eng False far the given Halt of Wel, G+ =(am.2) = aon-4% DANDC — MAKM'L av: : - 19 [ 159) fmax fmin| AN oS [a 4h 9 | x ~ Le ; : [a3 9] fs 607] Le catg 5) =a leae| aa petal | 3-19, v4 Be Ci 87 9 Nw ewes ti the total no. of > Let Ton) vepacsernts mayen) element compariso” made Tm = 9 penatl emall oo ) ne? n>} large DANDE = P-T(Ah)42, tM) = 2 TOM) +2 — a TOMY) = apo 42 TM) = 2 12 TON) 242 = Tay) 4 Giz Beton) = ¢. tng) a 1 ate STON gota (Mya) 4 TACT? © Kw ye dort pry 10) because i¢ 0,60 a pic carte qn O mk-p¥ fry, heb ya 7 toe nat yet 7 We yn VC): ten) — ol hCaler)a 7 4 i |et ny C22 M ae Principle 0 y ‘i L208 12614, ? mM elements LOY, GS 1s Pr - | mo. ot ee 6 x j= Meraing - CE bf) @ UGA) (Space cmplexixy) — panve SC)= CL Sp Sp = 7d agr? Chwlea MCohecte 280 an efements is eu J L2 \ a a UCB se TE « wre. Gane OED) [met 4 ~ = cnet)o @ a cH ce) OY Got 254 G03 “GO slo 65? FOI Ke? Ar 1229 26s 310 3st B 9 25 : ry pipe 2S 310 3S 423 450 % COMBENE = dim £r a [bvz, “8 ro Lf 6) Ho 135 > Lee ten) representing -time -compleniy of Danone - MSC) : TO) optim =e co, . Tt, 67° a i ne eera 4by) a bo Tm2) THM): ae Wa We ‘Tot My TOM)» T(M/)4 BM a i nese: fO0=N_ “tM)= 2 fer) 4 mM, J4 bnde, pul TON = uty) 4 ba +bY TO) = y TM7y) 42) — @& TOW = § 1(%¢) + 3b = 2) TC%z3) 4. 3b7. To) = 2k T(Hk)p-cbn -— @ Now) = 2k TO sak. r)$ by. k = V-C+ bn. hogy) TN= cn+by sean | q O(n40gn) a (nso) guile = [ ¢ 2-O(nL0gn) — uniform No. OF comparisoy? ivresmectve gf i/p . crevangernent ? SO) = fea, Si) Sp=(nt 7 + torn ) v Ln stetek fraus A Aw® §— Recs io 2 aes Merge Sort 7 : <7 9 A: 310) are) i499 te 679 cin dag che G07 G09 possi: tees ee, 6st) 392 423) C284 OD Tirso sza) fF pascr: CAI res gio cot) C2Sh B8l Uae eel} Cuse 5109 PCM fg cked (ed loll 423 652 6619 Cyso 20D cla9 754 2% 310 ast 422 USO sao ese EID 7 _[e atime no. of « comparisons, Lif eve a [riety = Ontos never rare toe? Nh 0, an[ (a) BINARY SEARCH ‘ 5 Ardy :«nlmear search - OC) Gd ner @W . mn 4c. @ #) O01) - Bese uceeseM d < OC t9n) — worst ® iL x unsicces shal - OC 109) ¥ Pull Binary Twee - Ani the levels have ” A max. possible nodes max. no. of nodes pA WJ ere é ‘ % Complek B.T. | she level ovdex index must pie to Chen) | phere n- total no of rides a0 Co) inde sr! => lovel, ar Wf t= & A ‘ i4 | oe ai) tis! Is ye Steicly BT. > J | vegvee vf vide & etther 0 Or 2 % Node ~ | Vy > Eves All BT 1 Oo Strictly 8.7. 3$ 7 ey Pa BINARY SEARCH ~ PAR cowie?) a(n, a roa DAvoc) an ) x) x Ok T¥-| Gh. n- CG MD) | ey (1%) 13 (A-K, Gen -- Gn) 21 Bs, n/- ¢M —» cet Ten) vepresentns timing Complexiy 1 : ot B.S) #Q Tm) = ¢ ) N=2 i =b+ TR) 7 yN>L (f Ton) = TRI +b — ay ‘. Per ner — Crem) = ON) 4 s | tn) =. TCM"y) #76. — @ et) +35 —@ e ta) = (Ah) 4 3b + Tem =T(Mye) + KE erajy4 bk FM = ct+b fog \ | Be AMR LTTEEs whut is the avewige v0. of key COMPA Tis a7 for success ul sequential seaych im a list having mm -€lemen &. neni DIN by My, Ler MD/y d> Org. wen iC Nite 423. “ i iia | [ avg. v0: Ot 1T3. q Camparison = [t2484-- 97 = omen atl mz Z Ext Consider a yariatim oF rnewe sor here | the list is divided Into 3 subprdblems instead oF 2. euch having nfz elements. By wing 3-U60/ maging Finctecid of z-uty to get the final sorting. Dene | the Recurrence fer nis variate” of merge | sm e dotermme 1 complexity, oF #ime 1 fof 6 | ee | =3-T°m%)+bn, N72 Y- W- | stem is O(% 404 n) DR. "3 combme. /~ /\~ . ny = tm= 3 (13) + bl _-O Tet. %+% =n A —— e | Tn) = 3- 1%) + 6% # | (TON = 3 [2 TONG) + bay] 4b oS —_@ ae | rom = 9. T(Mg) 4 27 = STM tZen | orem a Force) tebM take 1 = 3* Tm =u7. THF 4ogn bu i [rer afena a ] = sy [VE OY 2 2» | oe