Algorithms And Data Structures - Complexity Of Algorithms

Algorithmsand DataStructuresMarcinSydowAlgorithms and Data StructuresComplexity of AlgorithmsMarcin Sydow

Desired Properties of a Good AlgorithmAlgorithmsand DataStructuresMarcinSydowAny good algorithm should satisfy 2 obvious conditions:12correct (desired) output (for the given problem)be e ective ( fast )computead. 1) correctness of algorithmad. 2) complexity of algorithmComplexity of algorithm measures how fast is the algorithmtime complexity) and what amount of memory it usesspace complexity) - time and memory - 2 basic resources in((computations

Example - the Search ProblemAlgorithmsand DataStructuresMarcinSydowProblem ofsearching a key in an arrayWhat does the amount of work of this algorithm depend on?find(arr, len, key)Speci cation:input: arr - array of integers, len - it's length, key - integer to be foundoutput: integer 0stored i lenbeing the index in arr, under which the key is

Example - the Search ProblemAlgorithmsand DataStructuresMarcinSydowProblem ofsearching a key in an arrayWhat does the amount of work of this algorithm depend on?find(arr, len, key)Speci cation:input: arr - array of integers, len - it's length, key - integer to be foundoutput: integer 0 i lenbeing the index in arr, under which the key isstored (is it a complete/clear speci cation?)

Example - the Search ProblemAlgorithmsand DataStructuresMarcinSydowProblem ofsearching a key in an arrayWhat does the amount of work of this algorithm depend on?find(arr, len, key)Speci cation:input: arr - array of integers, len - it's length, key - integer to be foundoutput: integer 0 i lenbeing the index in arr, under which the key isstored (is it a complete/clear speci cation?) or the value of -1 when thereis no speci ed key in ( rst len positions of ) the array

Example - the Search ProblemAlgorithmsand DataStructuresMarcinSydowProblem ofsearching a key in an arrayWhat does the amount of work of this algorithm depend on?find(arr, len, key)Speci cation:input: arr - array of integers, len - it's length, key - integer to be foundoutput: integer 0 i lenbeing the index in arr, under which the key isstored (is it a complete/clear speci cation?) or the value of -1 when thereis no speci ed key in ( rst len positions of ) the arraycode:find(arr, len, key){i 0while(i len){if(arr[i] key)return ii }return -1}What does the amount of work of this algorithm depend on?

The speed of algorithmAlgorithmsand DataStructuresMarcinSydowHow to measure how fast (or slow) an algorithm is?There are 2 issues to be considered when designing such ameasure:1independence on any programming language (andhardware/software platform)2maximum independence on particular input dataIt should be an internal property of the algorithm itselfAny idea?

The speed of algorithmAlgorithmsand DataStructuresMarcinSydowHow to measure how fast (or slow) an algorithm is?There are 2 issues to be considered when designing such ameasure:1independence on any programming language (andhardware/software platform)2maximum independence on particular input dataIt should be an internal property of the algorithm itselfAny idea? Count basicoperations of the algorithm

Dominating OperationsAlgorithmsand DataStructuresMarcinSydowSimpli cation: it is not necessary to count all the operations - itis enough to count the representative onesBefore doing a complexity analysis2 steps must be done:1determine the dominating operation set2observe what (in input) in uences the number ofdata size)dominating operations (Dominating operations are those which cover the amount ofwork which is proportional to the whole amount of work of thealgorithm (they well represent the whole)

Example - determining operating operationsAlgorithmsand DataStructuresMarcinSydowWhat can be thealgorithm?dominating operation set in the followingfind(arr, len, key){i 0while(i len){if(arr[i] key)return ii }return -1}assignmenti 0?

Example - determining operating operationsAlgorithmsand DataStructuresMarcinSydowWhat can be thealgorithm?dominating operation set in the followingfind(arr, len, key){i 0while(i len){if(arr[i] key)return ii }return -1}assignmentcomparisoni 0 ? noi len ?

Example - determining operating operationsAlgorithmsand DataStructuresMarcinSydowWhat can be thealgorithm?dominating operation set in the followingfind(arr, len, key){i 0while(i len){if(arr[i] key)return ii }return -1}i 0 ? noi len ? yescomparison arr[i] keyassignmentcomparison?

Example - determining operating operationsAlgorithmsand DataStructuresMarcinSydowWhat can be thealgorithm?dominating operation set in the followingfind(arr, len, key){i 0while(i len){if(arr[i] key)return ii }return -1}i 0 ? noi len ? yescomparison arr[i] keyassignmentcomparisonboth the above? yes

Example - determining operating operationsAlgorithmsand DataStructuresMarcinSydowWhat can be thealgorithm?dominating operation set in the followingfind(arr, len, key){i 0while(i len){if(arr[i] key)return ii }return -1}i 0 ? noi len ? yescomparison arr[i] keyassignmentcomparison? yesboth the above? yesreturn statementreturn i?

Example - determining operating operationsAlgorithmsand DataStructuresMarcinSydowWhat can be thealgorithm?dominating operation set in the followingfind(arr, len, key){i 0while(i len){if(arr[i] key)return ii }return -1}i 0 ? noi len ? yescomparison arr[i] keyassignmentcomparison? yesboth the above? yesreturn ii ?return statementindex increment? no

Example - determining operating operationsAlgorithmsand DataStructuresMarcinSydowWhat can be thealgorithm?dominating operation set in the followingfind(arr, len, key){i 0while(i len){if(arr[i] key)return ii }return -1}i 0 ? noi len ? yescomparison arr[i] keyassignmentcomparison? yesboth the above? yesreturn ii ? yesreturn statementindex increment? no

Example, cont. - determining the data sizeAlgorithmsand DataStructuresMarcinSydowWhat is thedata size in the following algorithm?find(arr, len, key){i 0while(i len){if(arr[i] key)return ii }return -1}

Example, cont. - determining the data sizeAlgorithmsand DataStructuresMarcinSydowWhat is thedata size in the following algorithm?find(arr, len, key){i 0while(i len){if(arr[i] key)return ii }return -1}Data size:length of array arr

Example, cont. - determining the data sizeAlgorithmsand DataStructuresMarcinSydowWhat is thedata size in the following algorithm?find(arr, len, key){i 0while(i len){if(arr[i] key)return ii }return -1}Data size:length of array arrHaving determined thedominating operation and data sizewe can determine time complexity of the algorithm

Time Complexity of AlgorithmAlgorithmsand DataStructuresMarcinSydowDe nitionTime Complexity of Algorithm is the number of dominatingoperations executed by the algorithmas the function of datasize.Time complexity measures the amount of work done by thealgorithm during solving the problem in the way which isindependent on the implementation and particular input data.The lower time complexity the faster algorithm

Example - time complexity of algorithmAlgorithmsand DataStructuresMarcinSydowfind(arr, len, key){i 0while(i len){if(arr[i] key)return ii }return -1}Assume:dominating operation: comparison arr[i] keydata size: the length of array (denote by n)Thus, the number of dominating operations executed by thisalgorithm ranges:fromto1 (the key was found under the rst index)n (the key is absent or under the last index)There is no single function which could express the dependence of the number ofexecuted dominating operations on the data size for this algorithm.

Pessimistic Time ComplexityAlgorithmsand DataStructuresMarcinSydowlet's assume the following denotations:n - data sizeDn - the set of all possible input datasets of size nt (d ) - the number of dominating operations for dataset d (of size n)( d Dn )De nitionPessimistic Time Complexity of algorithm:W (n) sup{t (d ) : d Dn }(W(n) -Worst)Pessimistic Time Complexity expresses the number ofdominating operations in the worst case of input data of size nE.g. for our example the pessimistic time complexity is given bythe formula:

Pessimistic Time ComplexityAlgorithmsand DataStructuresMarcinSydowlet's assume the following denotations:n - data sizeDn - the set of all possible input datasets of size nt (d ) - the number of dominating operations for dataset d (of size n)( d Dn )De nitionPessimistic Time Complexity of algorithm:W (n) sup{t (d ) : d Dn }(W(n) -Worst)Pessimistic Time Complexity expresses the number ofdominating operations in the worst case of input data of size nE.g. for our example the pessimistic time complexity is given bythe formula:W (n ) n

Average Time Complexity of AlgorithmAlgorithmsand DataStructuresMarcinSydowlet's assume the following denotations:n - data sizeDn - the set of all possible input datasets of size nt (d ) - the number of dominating operations for dataset d (of size n) (d Dn )Xn - random variable, its value is t(d) for d Dnpnk - probability distribution of the random variable Xn (i.e. the probability thatfor input data of size n the algorithm will execute k dominating operationsk 0))(De nitionAverage Time Complexity of Algorithm:A(n) k 0 pnk · k PPP (Xn k ) · k(expected value of the random variable representing the numberof dominating operations)(A(n)Average)

Example - Determining the Average TimeComplexityAlgorithmsand DataStructuresMarcinSydowLet's determine the average time complexity for our exemplaryalgorithm ( nd)First, we have to assume someprobabilistic model of inputdata (i.e. the probabilistic distribution of possible inputdatasets)Let's make a simplistic assumption: the key to be found occursexactly once in array and with the same probability on eachk n P ( Xn k ) 1 / n )index (uniform distribution) ( 0 Thus:A(n) k 0 P (Xn k ) · k PPn 1k n 1/n · k 20

Space Complexity of AlgorithmAlgorithmsand DataStructuresMarcinSydowDe nitionS(n) is the number of unitsof memory used by algorithm as a function of data sizeSpace Complexity of Algorithm:This characteristic is more dependent on particular platform than time complexity.As a memory unit one can consider the machine word.Note:We will assume, that the memory used for keeping the inputdata is not considered because usually arrays (and othercompound types) are passed as arguments to functions byreference, which does not involve much memoryIn our example space complexity isconstant - because it consumes memory onlyfor a single variable (plus some xed number of additional temporal variables),independently on the input data size: S(n) const

Omitting Unimportant DetailsAlgorithmsand DataStructuresMarcinSydowimplementation of the algorithmparticular platforms by a constantmultiplicative factor. (e.g. CPU speed)The real time spent by anmay di er betweennotation allowing forexpressing the complexity functions with neglectingunimportant details (as multiplicative or additive constant, forThus, it would be very useful to have aexample)E.g. for the following function:A(n) 2.1 · n 1The most important information is that it is ait's rank of complexity is linearDoes such a notation exist?linear function -

Asymptotic Notation - Big O Algorithmsand DataStructuresMarcinSydowThe notation is called asymptotic notation .There are a couple of avours. The most common is big O :De nitionThe function g(n) isthe upper bound of rank of order of thefunction f(n):f (n) O (g (n)) c n0 n n0 f (n) c · g (n)0The O() notation intuitively corresponds to the symbol (interms of ranks of orders of functions).E.g. the fact that W(n) of our exemplary algorithm has anupper bound of the linear rank can be noted as:W (n ) n 12 O (n)The constant space complexity S(n) of that algorithm can beexpressed with the following special notation:S (n) O (1)