Extracting Performance FunctionsBasic OperationsBasic Operations: ExamplesCounting ProceduresCounting IF StatementsCounting LoopsInput Dependent LoopsCounting Nested LoopsAlgorithm PeculiaritiesRecursive FunctionsRecursion: An ExampleBoundary ConditionsExtracting Performance Extracting Performance FunctionsFunctionsBasic OperationsBasic OperationsThe number of Basic Operations performed The number of Basic Operations performed must be proportional to the run timemust be proportional to the run timeCounting techniques depend on control Counting techniques depend on control structuresstructuresThe Worst Case assumption is most commonThe Worst Case assumption is most commonAverage Case can be done for some Average Case can be done for some algorithmsalgorithmsBasic Operations: ExamplesBasic Operations: ExamplesSortingSortingKey-to-Key ComparisonsKey-to-Key ComparisonsSearchingSearchingKey-to-Unknown ComparesKey-to-Unknown ComparesMatrix Multiply Adds, or MultipliesMatrix Multiply Adds, or MultipliesGraph Operations Processing a VertexGraph Operations Processing a VertexPolynomial Evaluation Arithmetic Ops.Polynomial Evaluation Arithmetic Ops.Counting ProceduresCounting ProceduresStraight-Line Code:Straight-Line Code:–Simply Count the operations you seeSimply Count the operations you seeAssume basic operation is additionAssume basic operation is additiona := b + c - dc := x+5d := d * 3e := e + 1Total Operations = 3Counting IF StatementsCounting IF StatementsBasic Operation is AdditionBasic Operation is AdditionAssume Worst CaseAssume Worst CaseCount Only One SideCount Only One SideIf a = b+c Then c := d + e f := g + c + 1Else c := e + fEndifTotal Operations = 4Counting LoopsCounting LoopsAssume Worst-Case Number of IterationsAssume Worst-Case Number of IterationsCount Body, Multiply by Iteration CountCount Body, Multiply by Iteration CountAssume Basic Operation is AdditionAssume Basic Operation is AdditionFor i := 1 to 12 do a := b+c d := d + 7End ForTotal Operations = 24Input Dependent LoopsInput Dependent LoopsIf the number of iterations depends on the If the number of iterations depends on the size of the input, size of the input, nn, then the count is a , then the count is a function of function of nnFor i := 1 to n do a := b+c d := d + 7End ForTotal Operations = 2nCounting Nested LoopsCounting Nested LoopsThe following rules of thumb The following rules of thumb usuallyusually apply apply–A single loop yields a linear function of A single loop yields a linear function of nn–A doubly-nested loop yields a function of A doubly-nested loop yields a function of nn22–A triply-nested loop yields a function of A triply-nested loop yields a function of nn33Be Careful when applying these rulesBe Careful when applying these rulesFor i := 1 to n do For j := 1 to n do a := a + 1 End ForEnd ForTotal Operations = n2For i := 1 to n do For j := 1 to 3 do a := a + 1 End ForEnd ForTotal Operations = 3nAlgorithm PeculiaritiesAlgorithm PeculiaritiesIt is necessary to take the peculiarities of an It is necessary to take the peculiarities of an algorithm into account when counting operationsalgorithm into account when counting operationsi := 1; Cond := ExternalFunction( );While (i<n) And (Cond) do a := a + 1; Cond := ExternalFunction( ); i := i + 1;End While;For j := i to n do a := a + 1;End For;Total Operations = nRecursive FunctionsRecursive FunctionsDefine W(Define W(nn) as the number of operations ) as the number of operations done for input of size done for input of size nnWhen encountering a recursive call, add When encountering a recursive call, add W(x) where x is the size of the input for the W(x) where x is the size of the input for the recursive callrecursive callMore work must be done to obtain a usable More work must be done to obtain a usable solutionsolutionRecursion: An ExampleRecursion: An ExampleBasic Operation is MultiplicationBasic Operation is MultiplicationSize of input is Value of Size of input is Value of xxFunction Fact(x: integer):Integerbegin If x < 1 Then Fact = 1; Else Fact := Fact(x-1)*x; End IfendW(n) = W(n-1) + 1Boundary ConditionsBoundary ConditionsThe Equation W(n) = W(n-1) + 1 is called A The Equation W(n) = W(n-1) + 1 is called A Recurrence RelationRecurrence RelationIt Must be solved to remove the reference to It Must be solved to remove the reference to W on the right hand sideW on the right hand sideSolution requires a boundary condition of Solution requires a boundary condition of the form W(the form W(aa) = ) = kk for constants for constants aa and and kkIn the In the FactFact example: W(0) = 0 example: W(0) =