T&RTeamofAlgorithmDesignCollegeofComputerScienceandEngineering,CQUAlgorithmAnalysis&Design

IntroductiontoAlgorithmChapter3:AsymptoticAnalysisforAlgorithmsOutline3.1ASYMPTOTICANALYSIS&LANDAUSYMBOLS3.2ANALYSISofOPERATIONS3.1ASYMPTOTICANALYSIS&LANDAUSYMBOLSBackgroundSupposewehavetwoalgorithms,howcanwetellwhichisbetter?Wecouldimplementbothalgorithms,runthembothExpensiveanderrorpronePreferably,weshouldanalyzethemmathematicallyAlgorithmanalysisBackgroundWithoutalgorithmanalysis,therewillalwaysbelingeringquestions:Wasthealgorithmimplementedcorrectly?Arethereanybugs?Howmuchfaster?BackgroundYoumayhaveheardthatonyourwork-termreports,youshouldusequantitativeanalysisinsteadofqualitativeanalysisThesecondreferstocomparisonofqualities,e.g.,faster,lessmemory,etc.Engineersmustdeterminetheactualcosts(memory,time,monetary)involvedwiththealgorithmstheyproposeAsymptoticAnalysisIngeneral,wewillalwaysanalyzealgorithmswithrespecttooneormorevariablesWewillbeginwithonevariable:ThenumberofitemsncurrentlystoredinanarrayorotherdatastructureThenumberofitemsexpectedtobestoredinanarrayorotherdatastructureThedimensionsofann×nmatrixExampleswithmultiplevariables:DealingwithnobjectsstoredinmmemorylocationsMultiplyingak×mandanm×nmatrixDealingwithsparsematricesofsizen×nwithmnon-zeroentriesFindtheKeyIndexForexample,wecanchecktherequiredtimetosearchforacertainvalueinasorted,n-element-arrayWefirstapplythelinearsearch intfind_keyIndex(int*array,intn,intkey){

intresult=-1; for(inti=1;i<n;++i){ if(array[i]==key){ result=i;

break; } } returnresult; }Theaveragecomparisoncountforlinearsearchwouldben/2FindtheKeyIndexAndthenweapplythebinarysearchintbinary_search(int*a,intn,intkey){

intmid,front=0,back=n-1;

while(front<=back){

mid=(front+back)/2;

if(a[mid]==key)

returnmid;

if(a[mid]<key)

front=mid+1;

else

back=mid-1;

}

return-1;

}Theaveragecomparisoncountforbinarysearchwouldbelog(n/2)LinearandBinarySearchThisplotshowsmaximumandaveragenumberofcomparisonstofindanentryinasortedarrayofsizenLinearsearchBinarysearchWeseethanthegrowthof

linearsearchandbinary

searchareverydifferent.Howaboutthefunctions

withthesameorder?nConsiderthetwofunctions f(n)=n2

g(n)=n2–3n+2Aroundn=0,theylookverydifferentQuadraticGrowthQuadraticGrowthIfwelookataslightlylargerrangefromn=[0,10],webegintonotethattheyaremoresimilar:QuadraticGrowthExtendingtherangeton=[0,100],thesimilarityincreases:QuadraticGrowthAndontherangen=[0,1000],theyare(relatively)indistinguishable:QuadraticGrowthThearedifferentabsolutely,forexample, f(1000)=1000000 g(1000)=997002However,thisrelativedifferenceisverysmall:Andthisdifferencegoestozeroasn→∞PolynomialGrowthTodemonstratewithanotherexample, f(n)=n6

g(n)=n6–23n5+193n4–729n3+1206n2–648nAroundn=0,theyareverydifferentPolynomialGrowthEvenextendingtherangeton=[0,10]doesnotappeartogivemuchsimilarityPolynomialGrowthHowever,asweextendtherangeto[0,100],theyappeartolookalotmoresimilar:PolynomialGrowthAndfinally,aroundn=1000,therelativedifferenceislessthan3%PolynomialGrowthThejustificationforbothpairsofpolynomialsbeingsimilaristhat,inbothcases,theyeachhadthesameleadingterm: n2inthefirstcase n6inthesecondPolynomialGrowthSupposehowever,thatthecoefficientsoftheleadingtermsweredifferentInthiscase,bothfunctionswouldexhibitthesamerateofgrowth,however,onewouldalwaysbeproportionallylargerCountingInstructionsSupposewehadtwoalgorithmswhichsortedalistofsizenandthenumberofinstructionsisgivenby bworst(n)=4.5n2–0.5n+5 SortB

bbest(n)=3.5n2+0.5n+5 s(n)=4n2+8n+6 SortSThesmallerthevalueis,thefewerinstructionsarerunForn≤17,bworst(n)<s(n)Forn

≥18,bworst(n)>s(n)CountingInstructionsWithsmallvaluesofn,thealgorithmdescribedbys(n)requiresmoreinstructionsthaneventheworst-caseforsortb.

CountingInstructionsWithlargerandlargerlists,thenumberofinstructionsisessentiallyproportionaltotheleadingcoefficientsCountingInstructionsNearn=1000, bworst(n)

≈1.125s(n)

bbest(n)

≈0.875s(n)Isthisasignificantdifference?AsymptoticAnalysisGivenanalgorithm:WeneedtobeabletodescribethesevaluesmathematicallyWeneedasystematicmeansofusingthedescriptionofthealgorithmtogetherwiththepropertiesofanassociateddatastructureWeneedtodothisinamachine-independentwayForthis,weneedLandausymbolsandtheassociatedasymptoticanalysisAsymptoticAnalysisBigIdeaIgnoremachine-dependentconstantsLookatgrowth

of

T(n)as

n→∞.T(n):theAsymptoticRunningTimeNeglectsthefactthatthetimecostofeachstatementactuallydependsonthecompiler,interpreterandthehardwareplatformStandsfortheworstcaseT(n)canbedenotedorapproximatedbyafunctionf(n)LandauSymbolsBeforewebegin,however,wewillmakesomeassumptions:OurfunctionswilldescribethetimeormemoryrequiredtosolveaproblemofsizenWeconcludewearerestrictingourselvestocertainfunctions:Theyaredefinedforn≥0andn→∞TheyarestrictlypositiveforallnInfact,f(n)>cforsomevaluec>0Thatis,anyproblemrequiresatleastoneinstructionandbyteTheyarenon-decreasing(monotonicnon-decreasing)LandauSymbols-BigQf(n)=Q(g(n)),ifthereexistpositiveconstantsc1,

c2,andn0

suchthat

0≤c1

g(n)≤f(n)≤c2

g(n)foralln≥n0

}Thefunctionf(n)hasarateofgrowthequaltothatofg(n)LandauSymbols-BigQThesedefinitionsareoftenunnecessarilytediousNote,however,thatiff(n)andg(n)arepolynomialsofthesamedegreewithpositiveleadingcoefficientssuchthat:

whereLandauSymbols-BigQSupposethatf(n)andg(n)satisfyFromthedefinition,thismeansgiven

c>e

>0thereexistsann0

>0suchthat

whenevern>n0Thatis,LandauSymbols-BigQThus,thestatement

saysthatf(n)=Q(g(n))Notethatthisonlygoesoneway:Ifwhere,itfollowsthat

f(n)=Q(g(n))BigQasanEquivalenceRelationActually,f(n)=Q(g(n))describesanequivalencerelation: 1.f(n)=Q(g(n))ifandonlyifg(n)=Q(f(n)) 2.f(n)=Q(f(n)) 3.Iff(n)=Q(g(n))andg(n)=Q(h(n)),itfollowsthatf(n)=Q(h(n))Consequently,wecangroupallfunctionsintoequivalenceclasses,whereallfunctionswithinoneclassarebig-thetaQ

ofeachotherBigQasanEquivalenceRelationForexample,allofn2

100000n2–4n+19 n2+1000000 323n2–4nln(n)+43n+10 42n2+32 n2+61nln2(n)+7n+14ln3(n)+ln(n)

arebig-Q

ofeachother E.g.,42n2+32=Q(323n2–4nln(n)+43n+10)BigQasanEquivalenceRelationForsimple,weselectoneelementtorepresenttheclassofthesefunctions:n2Wecouldchoseanyfunction,butthisisthesimplestDrop

low-ordertermsIgnore

leadingconstants.Example:3n2

+90n–5logn+6046=Θ(n2)DropIgnoreBigQasanEquivalenceRelationThemostcommonclassesaregivennames:

Θ

(1) constant

Θ

(log(n)) logarithmic

Θ

(n) linear

Θ

(nlog(n)) “nlogn”

Θ

(n2) quadratic

Θ

(n3) cubic

Θ

(n!)

factorial 2n,en,4n,... exponentialBigQasanEquivalenceRelationWhenngetslargeenough,aΘ(n2)algorithmalwaysbeatsaΘ(n3)algorithm.T(n)nn0Θ(n2)Θ(n3)BigQasanEquivalenceRelationRecallthatalllogarithmsarescalarmultiplesof

eachother:Thereforelogb(n)=Θ(ln(n))foranybasebAlternatively,thereisnosingleequivalenceclassforexponentialfunctions:If1<a<b,However,wewillseethatitisalmostuniversallyunacceptabletohaveanexponentiallygrowingfunction!BigQasanEquivalenceRelationPlotting2n,

en,and4nontherange[1,10]alreadyshowshowsignificantlydifferentthefunctionsgrow Note:210=1,024e10≈22,026410=1,048,576LandauSymbols-BigOf(n)=O(g(n)),ifthereexistpositiveconstantsc

andn0

suchthat0≤f(n)≤c·g(n)foralln≥n0

}SimilartobigQ,wehaveanotherdefinitionthat

Ifwhere,itfollowsthat

f(n)=O(g(n))LandauSymbols-BigOExample:2n

+10isO(n)Proof:2n

+10

cn

=>(c

2)n

10

=>n

10/(c

2)

Pickc=3andn0=10LandauSymbols-BigOExample:n2isnotO(n)Proof:

n2

c·n

=>n

c

Theaboveinequality

cannotbesatisfied

sincecmustbea

constantwhile

n→∞LandauSymbols-BigO3n3

+20n2+5isO(n3)needc>0andn0

1suchthat

3n3+20n2+5

cn3forn

n0

=>trueforc=4andn0=213logn+5isO(logn)needc>0andn0

1suchthat

3logn+5

clogn

forn

n0

=>trueforc=8andn0=2GeneralRulesforcalculatingBigOIgnoreleadingconstants.Ford>0,O(f(n))=O(d·f(n)).

Proof:

O(f(n))=g(n)=>f(n)≤c·g(n)foralln≥n0

=>d·f(n)≤c·d·g(n)foralln≥n0Thus,wepracticallyprefersayingthatthetimecomplexityofprogramAisO(n)ratherthanO(6n).GeneralRulesforcalculatingBigODroplow-orderterms.2n+n3isO(2n).

Proof:

needc>0andn0

1suchthat

2n+n3

c·2n

forn

n0

=>trueforc=2andn0=10

=>actually,wecandropn3atthebeginning

sinceEveryexponentialgrowsfasterthanapolynomial.TightnessofBigO3n3+20n2+5isO(n3)Naturally,wecanprovethat3n3+20n2+5isO(n4)WegenerallypreferatightboundonbigO(orelsethebigΘ),whenwecanproveit.However,anupperboundisacceptableundermanycircumstancesTightbound,=Θ(n3)NotatightboundBig-OhOperationsO(f(n))+O(g(n))=O(max{f(n),g(n)})O(f(n))+O(g(n))=O(f(n)+g(n))O(f(n))·O(g(n))=O(f(n)·g(n))O(c·f(n))=O(f(n))ImportantFunctionsThemostcommonclassesaregivennames:

O

(1) constant

O

(log(n)) logarithmic

O

(n) linear

O

(nlog(n)) “nlogn”

O

(n2) quadratic

O

(n3) cubic

O

(n!)

factorial 2n,en,4n,... exponentialO(n)h=0

for(i=0;i<n;i++)

{

h+=i;

}O(n2)h=0;

for(i=0;i<n;i++)

{

for(j=0;j<n;j++)

{

h+=i*j;

}

}O(n2)h=0;for(i=0;i<n;i++)

{

for(j=0;j<i;j++)

{

h+=i*j;

}

}Sincethesecondloopdependsonthefirst,wecandenotetheloopingstepnumberby

whichisO(n2).O(log

n)h=0,k=1;while(k<=n)

{

h+=k;

k=2*k;

}Inthiscase,theindexkjumps(i.e.ktakesonvalues{1,2,4…})tillnisexceeded.Therewillbelog

(n)+1steps,thereforethecomplexityisO(log

n).LandauSymbols-BigOf(n)=O(g(n)),ifthereexistpositiveconstantsc

andn0

suchthat0≤f(n)≤c·g(n)foralln≥n0

}SimilartobigQ,wehaveanotherdefinitionthat

Ifwhere,itfollowsthat

f(n)=O(g(n))LandauSymbols-BigΩf(n)=Ω(g(n)),ifthereexistpositiveconstantsc

and

n0

suchthat0≤c·g(n)≤f(n)foralln≥n0

}SimilartobigQ,wehaveanotherdefinitionthat

Ifwhere,itfollowsthat

f(n)=Ω(g(n))TheRelationshipbetweenΘ,OandΩO

-Upperbounds.f(n)isO(g(n))ifthereexistconstantsc>0andn0≥0suchthatforalln≥n0wehavef(n)≤c·g(n).Ω-Lowerbounds.f(n)isΩ(g(n))ifthereexistconstantsc>0andn0

≥0suchthatforalln≥n0wehavef(n)≥c·g(n).Θ-Tightbounds.f(n)isΘ(g(n))iff(n)isbothO(g(n))andΩ(g(n)).IntuitionforΘ,OandΩO

f(n)isO(g(n))iff(n)isasymptoticallylessthanorequaltog(n)Ωf(n)isΩ(g(n))iff(n)isasymptoticallygreaterthanorequaltog(n)Θf(n)isΘ(g(n))iff(n)isasymptoticallyequaltog(n)AnotherIntuitionforΘ,OandΩO

f(n)=O(g(n))a

bΩf(n)=Ω(g(n))a

bΘf(n)=(g(n))a=bf(n)c·g(n)ExampleforΘ,OandΩf(n)=32n2+17n+32f(n)isO(n2),O(n3)f(n)isΩ(n2),Ω(n)f(n)isΘ(n2)f(n)isnotO(n)f(n)isnotΩ(n3)f(n)isneitherΘ(n)norΘ(n3)FiveLandauSymbolsWesometimesusethesefivepossibledescriptions:FiveLandauSymbolsGraphically,wecansummarizetheseasfollows:

WesayifInthefollowing,weintendtousebigOandbigΘmostly.Outline

Inthistopic,wewillexaminecodetodeterminetheruntimeofvariousoperations Wewillcalculatetheruntimesof:Operators +,-,=,+=,++,etc.Controlstatements if,for,while,do-while,switchFunctionsRecursivefunctions3.2ANALYSISofOPERATIONS

Motivation

ThegoalofalgorithmanalysisistotakeablockofcodeanddeterminetheasymptoticruntimeorasymptoticmemoryrequirementsbasedonvariousparametersGivenanarrayofsizen:SelectionsortrequiresQ(n2)timeMergesort,quicksort,andheapsortallrequireQ(nlog(n))timeHowever:MergesortrequiresQ(n)additionalmemoryQuicksortrequiresQ(log(n))additionalmemoryHeapsortrequiresQ(1)memoryMotivation TheasymptoticbehaviorsofalgorithmsindicatestheabilitytoscaleSupposewearesortinganarrayofsizen SelectionsorthasaruntimeofQ(n2)

2nentriesrequires(2n)2=4n2Fourtimesaslongtosort10nentriesrequires(10n)2=100n2OnehundredtimesaslongtosortMotivation TheothersortingalgorithmshaveQ(nlog(n))runtimes2nentriesrequire(2n)log(2n)

=(2n)(log(n)+1)

=2(nlog(n))+2n10nentriesrequire(10n)log(10n)

=(10n)(log(n)+log(10))

=10(nlog(n))+10n*log(10) Ineachcase,itrequiresQ(n)moretime However:Mergesortwillrequiretwiceand10timesasmuchmemoryQuicksortwillrequireoneorfouradditionalmemorylocationsHeapsortwillnotrequireanyadditionalmemoryMotivation Ifwearestoringobjectswhicharenotrelated,thehashtablehas,inmanycases,optimalcharacteristics:ManyoperationsareQ(1)I.e.,theruntimesareindependentofthenumberofobjectsbeingstored Ifwearerequiredtostorebothobjectsandrelations,bothmemoryandtimewillincreaseOurgoalwillbetominimizethisincreaseMotivation Toproperlyinvestigatethedeterminationofruntimesasymptotically,wewilldiscussOperationsControlstatementsConditionalstatementsandloopsFunctionsRecursivefunctionsOperators

Becauseeachmachineinstructioncanbeexecutedinafixedtime,wemayassumeeachoperationrequiresafixedtimeThetimerequiredforanyoperatorisQ(1)including:Retrieving/storingvariablesfrommemoryVariableassignment

=Integeroperations +-*/%++--Logicaloperations &&||!Bitwiseoperations &|^~Relationaloperations

==!=<<==>>Memoryallocationanddeallocation newdeleteOperators Ofthese,memoryallocationanddeallocationaretheslowestbyasignificantfactorAquicktestonunixshowsafactorofover100TheyrequirecommunicationwiththeoperationsystemThisdoesnotaccountforthetimerequiredtocalltheconstructoranddestructor Notethataftermemoryisallocated,theconstructorisrunTheconstructormaynotruninQ(1)timeBlocksofOperations

EachoperationrunsinQ(1)timeandthereforeanyfixednumberofoperationsalsoruninQ(1)time,forexample:Swapvariablesaandbinttmp=a;a=b;b=tmp;Updateasequenceofvalues++index;prev_modulus=modulus;modulus=next_modulus;next_modulus=modulus_table[index];

BlocksinSequence Supposeyouhavenowanalyzedanumberofblocksofcoderuninsequencetemplate<typenameT>voidupdate_capacity(intdelta){

T*array_old=array; intcapacity_old=array_capacity;

array_capacity+=delta; array=newT[array_capacity];

for(inti=0;i<capacity_old;++i){ array[i]=array_old[i]; } delete[]array_tmp;} Tocalculatethetotalruntime,addtheentries:Q(1+n+1)=Q(n)Q(1)Q(n)Q(1)BlocksinSequence Otherexamplesinclude:RunthreeblocksofcodewhichareQ(1),Q(n2),and

Q(n)

total

runtimeQ(1+n2+n)=Q(n2)RuntwoblocksofcodewhichareQ(nlog(n)),and

Q(n1.5)

totalruntimeQ(nlog(n)+n1.5)=Q(n1.5) Whenconsideringasum,takethedominanttermControlStatements Nextwewilllookatthefollowingcontrolstatements ThesearestatementswhichpotentiallyaltertheexecutionofinstructionsConditionalstatements

if,switchCondition-controlledloops

for,while,do-whileCount-controlledloops

forifrom1to10do...enddo;Collection-controlledloops

foreach(intiinarray){...}ControlStatements Givenanycollectionofnestedcontrolstatements,itisalwaysnecessarytoworkinsideoutDeterminetheruntimesoftheinner-moststatementsandworkyourwayoutControlStatements Givenif(condition){//truebody}else{//falsebody} Theruntimeofaconditionalstatementis:theruntimeofthecondition(thetest),plustheruntimeofthebodywhichisrun Inmostcases,theruntimeoftheconditionisQ(1)ControlStatements

Insomecases,itiseasytodeterminewhichstatementmustberun:

intfactorial(intn){ if(n==0){ return1; }else{ returnn*factorial(n–1); } }ControlStatements

Inothers,itislessobviousFindthemaximumentryinanarray: intfind_max(int*array,intn){ max=array[0]; for(inti=1;i<n;++i){ if(array[i]>max){

max=array[i]; } } returnmax; }AnalysisofStatements Inthiscase,wedon’tknow Ifwehadinformationaboutthedistributionoftheentriesofthearray,wemaybeabletodetermineitifthelistissorted(ascending)itwillalwaysberunifthelistissorted(descending)itwillberunonceifthelistisuniformlyrandomlydistributed,then???Condition-controlledLoops TheC++forloopisaconditioncontrolledstatement: for(inti=0;i<N;++i){ //... }

isidenticalto inti=0; //initialization while(i<N){ //condition //... ++i; //increment }Condition-controlledLoops

Theinitialization,condition,andincrementusuallyaresinglestatementsrunninginQ(1) for(inti=0;i<N;++i){ //... }

Condition-controlledLoops Theinitialization,condition,andincrementstatementsareusuallyQ(1) Forexample,for(inti=0;i<n;++i){//...} Thus,theruntimeisatW(1),thatis,atleasttheinitializationandoneconditionmustoccurCondition-controlledLoops Ifthebodydoesnotdependonthevariable(inthisexample,i),thentheruntimeof

for(inti=0;i<n;++i){//codewhichisTheta(f(n))}

isQ(nf(n)) IfthebodyisO(f(n)),thentheruntimeoftheloopisO(nf(n))Condition-controlledLoops Forexample,

intsum=0; for(inti=0;i<n;++i){ sum+=1;Theta(1) } Thiscodehasruntime Q(n·1)=Q(n)Condition-controlledLoops Anotherexampleexample,intsum=0;for(inti=0;i<n;++i){for(intj=0;j<n;++j){sum+=1;Theta(1)}}

ThepreviousexampleshowedthattheinnerloopisQ(n),thustheouterloopis Q(n·n)=Q(n2)ConditionalStatements ConsiderthisexamplevoidDisjoint_sets::clear(){

if(sets==n){return;}max_height=0;num_disjoint_sets=n;for(inti=0;i<n;++i){

parent[i]=i;tree_height[i]=0;}}Q(n)Q(1)Q(1)Q(1)AnalysisofRepetitionStatements Supposewitheachloop,weusealinearsearchanarrayofsizem:for(inti=0;i<n;++i){ //searchthroughanarrayofsizem

ExecutionBody //O(m);} TheinnerloopisO(m)andthustheouterloopis

O(n·m)

AnalysisofRepetitionStatements Ifthebodydoesdependsonthevariable(inthisexample,i),thentheruntimeoffor(inti=0;i<n;++i){//codewhichisTheta(f(i,n))}

is ;andifthebodyis

O(f(i,n)),thentheresultisAnalysisofRepetitionStatements Forexample, intsum=0; for(inti=0;i<n;++i){ for(intj=0;j<i;++j){ sum+=i+j; } } TheinnerloopisO(1+i(1+1))=Q(i)hence

theouterisAnalysisofRepetitionStatements

Asanotherexample: intsum=0; for(inti=0;i<n;++i){ for(intj=0;j<i;++j){ for(intk=0;k<j;++k){ sum+=i+j+k; } } } Frominsidetoout:

Q(1)

Q(j) Q(i2) Q(n3)ControlStatements

Switchstatementsappeartobenestedifstatements: switch(i){ case1:/*dostuff*/break; case2:/*dootherstuff*/break; case3:/*doevenmorestuff*/break; case4:/*well,dostuff*/break; case5:/*tiredyet?*/break; default:/*dodefaultstuff*/ }ControlStatements Thus,aswitchstatementwouldappeartoruninO(n)timewherenisthenumberofcases,thesameasnestedifstatementsThenwhynotuse: if(i==1){/*dostuff*/} elseif(i==2){/*dootherstuff*/} elseif(i==3){/*doevenmorestuff*/} elseif(i==4){/*well,dostuff*/} elseif(i==5){/*tiredyet?*/} else{/*dodefaultstuff*/}ControlStatements However,switchstatementswereincludedintheoriginalClanguage...why? First,youmayrecallthatthecasesmustbeactualvalues,either:integerscharacters Forexample,youcannothaveacasewithavariable,e.g.,

casen:/*dosomething*/break;//badControlStatements Thecompilerlooksatthedifferentcasesandcalculatesanappropriatejump Forexample,assume:thecasesare0,1,2,3,4,5,6,7,8,9,10eachcaserequiresamaximumof24bytes(forexample,sixinstructions) Thenthecompilersimplymakesajumpsizebasedonthevariable,jumpingaheadeither0,24,48,72,...,or240instructionsSerialStatements

Supposewerunoneblockofcodefollowedbyanotherblockofcode Suchcodeissaidtoberunserially IfthefirstblockofcodeisO(f(n))andthesecondisO(g(n)),thentheruntimeofbothtwoblocksis

O(f(n)+g(n)) whichusually(foralgorithmsnotincludingfunctioncalls)simplifiestooneortheotherSerialStatements Considerthefollowingtwoproblems:searchthrougharandomlistofsizentofindthemaximumentry,andsearchthrougharandomlistofsizentofindifitcontainsaparticularentry Whatisthepropermeansofdescribingtheruntimeofthesetwoalgorithms?SerialStatements Searchingforthemaximumentryrequiresthateachelementinthearraybeexaminedthus,itmustruninQ(n)time Searchingforaparticularentrymayendearlierforexample,thefirstentrywearesearchingformaybetheonewearelookingfor,thus,itrunsinO(n)timeSerialStatements

Therefore,iftheleadingtermisbig-Q,thentheresultmustbebig-Q,otherwiseiftheleadingtermisbig-O,wecansaytheresultisbig-O

Forexample,

O(n)+O(n2)+O(n4)=O(n+n2+n4)=O(n4) O(n)+Q(n2)=Q(n2) O(n2)+Q(n)=O(n2) O(n2)+Q(n2)=Q(n2)Functions

Afunction(orsubroutine)iscodewhichhasbeenseparatedout,eitherto:andrepeatedoperationse.g.,mathematicalfunctionsgrouprelatedtaskse.g.,initializationFunctions

Becauseasubroutine(function)canbecalledfromanywhere,wemust:preparetheappropriateenvironmentdealwitharguments(parameters)jumptothesubroutineexecutethesubroutinedealwiththereturnvaluecleanupFunctions

Fortunately,thisissuchacommontaskthatallmodernprocessorshaveinstructionsthatperformmostofthesestepsinoneinstruction Thus,wecanassumethattheoverheadrequiredtomakeafunctioncallandtoreturnisQ(1)Functions

Becauseanyfunctionrequirestheoverheadofafunctioncallandreturn,wewillalwaysassumethatTf=W(1) Thatis,itisimpossibleforanyfunctioncalltohaveazeroruntimeFunctions

Thus,givenafunctionf(n)(theruntimeofwhichdependsonn)wewillassociatetheruntimeoff(n)bysomefunctionTf(n)WemaywritethistoT(n) BecausetheruntimeofanyfunctionisatleastO(1),wew