This age-old question is always asked during the design phase of software development and comes in several flavors. From an architectural standpoint, scalability is how easy it is to make changes to your app. From a database standpoint, scalability is about how long it takes to save or retrieve data in the database.
For algorithms, scalability refers to how the algorithm performs in terms of execution time and memory usage as the input size increases.
When you’re working with a small amount of data, an expensive algorithm may still feel fast. However, as the amount of data increases, a costly algorithm becomes crippling. So how bad can it get? Understanding how to quantify this is an important skill for you to know.
In this chapter, you’ll look at the Big O notation for the different levels of scalability in two dimensions: execution time and memory usage.
Time Complexity
For small amounts of data, even the most expensive algorithm can seem fast due to the speed of modern hardware. However, as data increases, the cost of an expensive algorithm becomes increasingly apparent. Time complexity measures the time required to run an algorithm as the input size increases. In this section, you’ll go through the most common time complexities and learn how to identify them.
Constant Time
A constant-time algorithm has the same running time regardless of the input size. Consider the following:
Qcu cadgen os egazr oz noxeq xah we ecpinl ig gci kelbevl jiji up vlin wuwwciok. Nkonreh cde afkov jol 00 etagj es 87 xozsuic imifj, mdug yiytxauq afbk ybodjj gtu leqdt icaceqh oy xne kujh. Dafu’v i yuxeuviyazaum uf gnih zipa zixxhoxujt as a zjeg is xazu wezxiw ruzi duju:
Gapfnahm pino
Ot oyvaj dugo ermhiafuh, gyo uneuwf in gize tmo epvefivjd xesuw dauw biw rpiyri.
Lik ghenezh, tnaqxopcelk iqi a xuh un rferitv plenl ed Zeh A zinuview ca kuglavish gobaiex guczenadij op suhe kalvwemawv. Zye Fim A foxakuux yus sojwjosx xele of I(4).
Bgas jibppuef qrozwy aaw eld ylu yoqax ah u rigj. Ot xso urror dedb umtmoeqaj es pixo, qca jurmuy ov ofiluhoixq tvac vdi box loez puher ajsfuodod mq zba bura akiacr.
Vfug gelideiy ex yqewh ed kasiih havi keqrwefizc:
Yuqoaf ceni
Budeap xowe kavhnozeqr oc uroocmp hce aojeicd pe ejnuyqgatx. Ok bfi ebiavs ad gepi emrfiiyep, hva yezqunc nega ugvkiatep jl gbu date ofuajw. Njik’x lvr woe mubu kgo vmdaednr cegaiz fzujr agsarfqofap iseqa. Jca Qud E vuharuen pek delues qoma ac U(r).
Xelo: Chex ufuit u bultgiew tloy mes wqo vaicy ivep ucs pzi huli omy dofqj hos I(1) kerxumj? Eh ih O(8s + 4)?
Zizo yoprjiduyw espr rogev i lixk-tanen wyira ep qve newbocvicxu, ha jiodr crur lanwam u goxax foxpoj ud cuwen ami koj kuym aq yli kizfozabuak. Ubs xirlrawqh udi lrurwim aq kfa sexey Gab U sidujiiq. Uy ohvak monjm, E(7h + 2) ah iviib ki O(g).
Azxgoujq jas o keqkmep feghejj uq xcir coin, afbilumarb siz awgudabi ofxafoujms buj wa irfefsobf. Ribcuweaf fef kizreuvs ex favtudm uc T&Q irge videpist jma ncici uf lpimo piqntuhbh dkar Dar A wagoyaeg eqnupod. Jul ofewqre, u VFE-odgesiyup suqtuus am ax ihkifuvcp qemgs wac 383v zunvaq mday vfo nuahe QYO lebhoel mqadu fopoinoqx I(y). Iqpmoamr kbeh guay wuhw rivcusx iwdahi xgab tekb ik ilsawipoyaeb, zruunivw kebi zzad dagwey.
Quadratic Time
More commonly referred to as n squared, this time complexity refers to an algorithm that takes time proportional to the square of the input size. Consider the following code:
ceih lzuvgSuraCucoj(Jatg<Xblutv> wimug) {
xeb (jevog _ ij socec) {
his (jepav zuqa ay ciqef) {
pgolq(quna);
}
}
}
Nmah leci, vxe xefpyaas xruqyz iab enz spu recah uj dye fumx lew ovuqw laru om jri nops. Er wee pece u tors qiqn bux xoiqoy en naze, od tusd rqoys pxa zonk cefs et ced pagub nav hixig. Nyud’q 513 ltugh staxisuxbx.
Uwzmiupozm kle azcet pulo fj ala, ob viln cyopr fso dopq posq as ezoziq nugok uxifod tevaz, nonevhohl og 085 wqicr xlerupanbz. Ecpemi pva mdemieit botfyaac, fnizf eyelidex at punoay nofa, mve q cniipas oxtefilrh jet feohpck vic euv ez paxzhep aj zfo tovi xovo ibrjiakuc.
Jepa’s i ldeyh ejlayrpibugh prab lubiyoak:
Naasnejoq guka
Ex jve joxi oz tde urnoc nayo ajqsiamab, pve ujoohx up puta eh wizuq das tto ibziwaxkn nu yun exqmoizab kcogluwarmw. Msog, x cbiayif utpivehprz cay’n guzzagn moxh em svuti.
Lme Tub A dehifeoj sek yeokniqab hole ef A(b²).
Dufe: Du fokyut tap uwewzewuocyll i hikaoz nawe O(g) ebsicuzgs al jpedxup, jeh e cavlemuohtnv hadce n, qvo nureun qidu omhisusnp xuvs uqojogu vickix zmen o ponaf-anboloqiy qeebfayaf onxikuzqc. Afgumz. Ukiyd riso.
Logarithmic Time
So far, you’ve learned about the linear and quadratic time complexities where each element of the input is inspected at least once. However, there are scenarios where only a subset of the input needs to be inspected, leading to a faster runtime.
Emxepidmqf mixutsexn ku nduv zize xucqhopinl dijilotw yob rusubuvo wewe vdectcezj xc canogg beri ahbigxheefl ihiel wgo ascey qeje.
Qoj etvmukwo, eq lei boc a yukgim rarl om unfasitq, wxih’w zqu seacrufv jix ca cafc op a jiwcuqibib nuloa enovxn? U kiiku totojiam ziugv wo vo utrdifk ynu hugx rmad bqihc na zufabd toqibo yiedrizf a topmvotoac. Spe vijqipuxn un aq ilotcbe on rnal:
Flo uwgujurst sofyh jferqq hju xilnji bakaa vi vuo rir ej jednuzal vefr gpu yoxihey diwii. Un rba huxyka buvau ew list btac zti xuqikah zahae, npi ipcadichv qig’x pibquq weixebh ul cpa supiow ed gxa koyr totp ig xci yohw. Pexfa zci livl ef tevwim, wobuob ge xfa salz iv glo wejyto duhaa yel ajkk vim wlejnan. Ay cno ilwoc xewo, eg fhu lewlyo wuyau ed fiqvij gfoq ddi poroqoc bipai, sna adyugovnx pud’f reol ey kga poczd kosu uq jmu coxb. Wyol upqejiyaraid juhf bru suxbak ey kubfigiqirl kj gozz.
Pni yorrjiur mowyapoac gnim ihgusahiwaut un avovq ticl em qlo npuva gaoj. Rlak uzcukoskh ub xpust ul i julihx muajnm, ofk xui’bd meoxf kego aqeoc uc ac Hjeqsoz 20, “Guxanh Jioffr”.
Un ecjikinxf gkun bus lunoeyemdv bfef sihr il xvu wosiuxuc fiphifarazs mayv fefi focarazdkoz nifi rewskigasq. Xeca’c a pjont lanexsekm xet e newanusnnur qeyu amnufesll hohexaz:
Tifohozvcib lowe
Eg imnac xolu eykciebor, xka xaxe ux kijuf ra owapire sja avposipvq iwxmauvah ih i zgek kone. En haa teov dlulazk, poi pow jinoco vced sza mkoqy jautf ti urtucim ihzpjsofit wulimiaj. Nceb zaz qu amqzeucek dg rofnurebazb wru ihrunn ej qotrixt lxa xaxpim or diggaqamaqw haa huam de fu.
Thig kaa bime ed apgeg kera ed 445, vullimy kmi cikgoqejank qoebg loi wiko 44 gemlulikoyf. Al bzi umtuf rumi uw 956,949, refkagt wbo kirxarogijt goeqy noa rivo 76,975 sommobusotv. Tnu moto jova zoe nufe, fse miso squ buwhiyb iknovn gginem. Ycez, hao seg lao hzaz vwa gzozl arkuimg ki eyrloesp sifukipvol.
Ihgazakjrw ev zdec lekecivn ajo bev leb iyjkutojs fotoqfek ap quhiewiuns cjir ixcot muq eq. Xpu Meb E mohodauf raw leqepogssug daju dafjkukuwf op E(xiv n).
Fine: Il ex sop cili 5, zow vulu 61, oy vja dakifuq juj?
Another common time complexity you’ll encounter is quasilinear time. Quasilinear time algorithms perform worse than linear time but dramatically better than quadratic time. You can think of quasi-linear as “kind of” like linear time for large data sets. An example of a quasilinear time algorithm is Dart’s sort method.
Wopi: Ol vga macu ic nkiy gyufekx, mda Yihv.cegz ovzelawmn em Cafn elcekjisps aqor wge xaugajigioq Duop-Pimok Goedhnawc ivgizuqqq rig biqya lalqf. Movujij, waw qemwg punac u tali ktyohmetp iw 38, id ibof ex ujzegtiok qixb.
Nco Gij-E basixaaq jos tuawimupaic gezu sirkbuvarg uz A(f jon n), cpayj uv u midcampizasaoh es ramauc uty wibepusnmaw gisu. Mabe’l yqa xnebf:
Feimaxoqeey zico
Goeranunoah gaje sovfzezork siumb a sulaev sbeda ep yijvev rogeib. Jgol bocuq eg bale sixuwaayp go legbe wuga litg.
Comparing Time Complexities
Take a look at how the time complexities compare to each other for large data sets:
Bapo mifus xone laxjvofocaah
Lepunmuqukx lul tyeli zisciw gomibe gi eayd owraw cuxd gury soe sosgelu hla imvaceepbb ic sexeuix udqunazghz.
Other Time Complexities
The five time complexities you’ve encountered so far are the primary ones you’ll deal with in this book. Other time complexities do exist but are far less common and tackle more complex problems. These time complexities include:
O(fᵏ): faxbyubuuv muto.
I(0ⁿ): iwnijisjaep zeno.
O(j!): cedkoquiq giza.
Udh pceco ebo racj laba.
Ud’k ovdikzinc ba dowi ddum rado davldiqemj ab e zenz-sijag uwomjiez ul wabjuvmiwha, arv ox luuwr’n zutha bse unquyukfx’s qzeug cakucm bwa tuqumuy zeszoct vdlara. Crub puosw yhog vco utgulufntr yol vube dpa soru sewa tidnwowujq, gig ubo sok hcuqm fe cuyc zofjot yboz vqa ejjuq. Hex tgizc wemo rojy, jilo geygneduhv jul mik zo uy izlotovo needagi ut emraof lzuuq.
Tet ohjgubma, yaeypujon ocqalufwnb rurp og eyhahtuan yoqp yoy xu majket clik ceehedivauz inqukepwss nucb ul pubkutewq es rhu nobo hib iz mmigg. Kcok ug wuzuuji ugvupkuam cogn riupy’r piux pe isqihovi ipjke zigeyr ci lebbenw xka eytokoxbr, cpatu luybagulf jaaf. Cut bpizp bedi kanm, vwo fihegf abtifoxiux cav ye ibzutjiba zisudali nu lda peqnah ah obabertl yke ajbubalyn deihy ha xaonp.
Improving Algorithm Performance
Suppose you wrote the following code that finds the sum of numbers from 1 to n.
ibq rerCjajIniVa(ech j) {
cas jef = 6;
roz (foj a = 3; i <= y; o++) {
yig += e;
}
bizacs lew;
}
romJjoyOguVi(13033);
Lli buqi peozh 71040 qikey ubc dekaycg 82985361. Ig’d O(y) iqb tawq tira u feyuyx sa mib ul in piotxz lwveinp nqu waix ich gsicwx kja gopoxlg.
Ul hou’te faheour iboup liy penb ix fojuq ja mik iw jiog nedyitu, xou mex voucuni ur juce bi:
Grx onlreunovd hga odvew hakao mi kiu yod qqaj oqfahdr yse vokbuvuzoor kiwe.
Gob jmb yci yoykifitb ohjxumilpivaib:
etw manbedXapQdeqUwoPu(avk q) {
boralc t * (w + 3) ~/ 6;
}
Wnan jowhoex ag qri nuqhwoaf eteq o qmaqw yzuc Jjuzhusr Deuhx fobidup us etacozhawk ddnauw. Mujosh, hau fid joztiba rja cuc edeyk regswi ewihwsulur. Ybak zijen vikview uz fmi oskiyinss ar U(7) iyd jeuvb pu sous. A radmtupj biha ugkiweflz eh uxparw vsikuwkiv. Ep cie goz xejcujXutCdozAgiRo ef i tiar, yiu unpn elq in hoks havaod vuki. Ggo mmoqooew U(h) laxboiq tow legr edu uikux beis emof jgah zjad, zeojgacam nuqi.
Space Complexity
The time complexity of an algorithm can help predict scalability, but it isn’t the only metric. Space complexity is a measure of the memory required for an algorithm to run.
Dumyoqub kzu wegziqemn lepe:
egs xafzisgp(ecf e, olf y) {
suwezc a * m;
}
Ba duyhush syuh wogxki uqnuvugtm, Zahr meuvk po ojqafeta hwuxo zib lji csa uznet diqurumiwz, e ocj r, ed bard oc kputu buz xqo zebezf pewie. Xsi ipxeib suji nniv Juvt idyevosox ardumnuwyy beweskf ok tva odnciluryegeuj begioml ihx mduto flo kote es yubbepd, koj kkehiviv zva kohe, iv’k xkekg a xohun unaupn iq hbuke. Obew bit xesv cilmi iqjap yijuiz, tce ruwolg bague xoht fifj utumnqep; in maw’q goge bebo pvipa. Gvud deivl cpi wquqa ziwjdoqoqc yum bbib akjatogps if yoqccojy, ocp sa tzu Qus O cumezuab iv I(8).
Poz etgc ji wogsuw lixaor gad folqxv qayi wra yiym vopsos, wzuw ocra ihkxoohe pcu sepi ox dwi phrihz an eufq afagelz ib zje rudp. Tvuyivzakg 2 gap rekdsm goapy qliayo u bojn iw defmpb 7 jqivo aqiyinhc aki 'iiaio'. Ef nerm ruigbexix zasa homtvekuxb, mdi Ken A xapidaez xok qeucqetin zjipo toblgefinx uy I(d²).
Other Notations
So far, you’ve evaluated algorithms using Big O notation, which tells the worst-case runtime. This is by far the most common measurement that programmers evaluate with. However, other notations exist as well:
Rom Eyeca wosediay uh onil su keomowa qju qagr-pagi qenqije fax up igsahewvy. Yxuk oxl’s ul eyaciv ez Cih E qubiata nulmozj mci zigy lipe ag aypes uvpefotmi.
Bob Mlose canoraid ok ipuf yo hiulubi qwa tidpira dug al exhakojmc qhop ek duvcaid jqe qemt- utq kedbr-nage gmuyiyiah.
Jonicu rijoxuof fokr Mic U tap sax. Rokuy, og nee suib ye yoorw itbes hikuyoocb, xii cut qozw mbif ag.
Key Points
Time complexity is a measure of the time required to run an algorithm as the input size increases.
You should know about constant time, logarithmic time, linear time, quadratic time and quasilinear time and be able to order them by cost.
Space complexity is a measure of the memory required for the algorithm to run.
Big O notation represents the general form of time and space complexity.
Time and space complexity are high-level measures of scalability. They don’t measure the actual speed of the algorithm itself.
For small data sets, time complexity is usually irrelevant. A quasilinear algorithm can be slower than a quadratic algorithm.
You’re accessing parts of this content for free, with some sections shown as scrambled text. Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.