TimeComplexity

Information about TimeComplexity

Published on March 9, 2014

Author: lakshmitharun

Source: authorstream.com

Content

Time Complexity UC Berkeley Fall 2004, E77 http://jagger.me.berkeley.edu/~pack/e77 Copyright 2005, Andy Packard. This work is licensed under the Creative Commons Attribution-ShareAlike License. To view a copy of this license, visit http://creativecommons.org/licenses/by-sa/2.0/ or send a letter to Creative Commons, 559 Nathan Abbott Way, Stanford, California 94305, USA. : Time Complexity UC Berkeley Fall 2004, E77 http://jagger.me.berkeley.edu/~pack/e77 Copyright 2005, Andy Packard. This work is licensed under the Creative Commons Attribution-ShareAlike License. To view a copy of this license, visit http://creativecommons.org/licenses/by-sa/2.0/ or send a letter to Creative Commons, 559 Nathan Abbott Way, Stanford, California 94305, USA. Time complexity of algorithms: Time complexity of algorithms Dependency of the time it takes to solve a problem as a function of the problem dimension/size Examples: Sorting a list of length n Searching a list of length n Multiplying a n × n matrix by an n × 1 vector Time to solve problem might depend on data Average-case time Best-case time data is well suited for algorithm (can’t be counted on) Worst-case time data is such that algorithm performs poorly (time-wise) Worst-Case gives an upper bound as to how much time will be needed to solve any instance of the problem. Example: N-by-N matrix, N-by-1 vector, multiply: Example: N-by-N matrix, N-by-1 vector, multiply Y = zeros(N,1); for i=1:N Y(i) = 0.0; for j=1:N Y(i) = Y(i) + A(i,j)*x(j); end end initialize space, c 1 N initialize “ for ” loop, c 2 N Scalar assignment, c 3 initialize “ for ” loop, c 2 N (3 accesses, 1 add, 1 multiply) c 4 End of loop, return/exit, c 5 End of loop, return/exit, c 5 Total = c 1 N+c 2 N+N(c 3 +c 2 N+N(c 4 +c 5 )+c 5 ) = (c 2 +c 4 +c 5 )N 2 + (c 1 +c 2 +c 3 +c 5 )N = c 6 N 2 + c 7 N N times N times Asymptotic Time complexity of algorithms: Asymptotic Time complexity of algorithms Dependency of the time it takes to solve a problem as a function of the problem dimension/size but formula may only be valid for “large” problems So, we keep track of “growth rates” of the computational workload as a function of problem dimension Order, called “big O” notation: Order, called “big O” notation Given two functions, f and g , say that “ f is of order g ” if there is a constant c , and a value x 0 such that So, apart from a fixed multiplicative constant, the function g is an upper bound on the function f valid for large values of its argument. Notation: write to mean “ f is of order g ”. Sometimes write to remind us what the arguments are labled. Not equality,but “belongs to a class”: Not equality,but “belongs to a class” Recall that means that there is a constant c , and a value n 0 such that The = sign does not mean equality! It means that f is an element of the set of functions which are eventually bounded by (different) constant multiples of g . Therefore, it is correct/ok to write Big O: Examples: Big O: Examples Example: Note: For all n , f is bounded above by 31 g Write or Big O: Examples: Big O: Examples Example: Note: For large enough n f is bounded above by 5 g Write or or Big O: Relationships: Big O: Relationships Suppose f 1 and f 2 satisfy: There is a value n 0 Then Hence Example 3: Generalization: Big O: Relationships: Big O: Relationships Suppose positive functions f 1 , f 2 , g 1 , g 2 , satisfy Then Why? There exist c 1 , c 2 , n 1 , n 2 such that Take c 0 =c 1 c 2 , n 0 =max ( n 1 ,n 2 ). Multiply to give Example: Asymptotic: Relationships: Asymptotic: Relationships Obviously, for any positive function g Let  be a positive constant. Then as well. Example 4: Message: Bounding of growth rate. If n doubles, then the bound grows by 8. Example 5: Example: N-by-N matrix, N-by-1 vector, multiply: Example: N-by-N matrix, N-by-1 vector, multiply Y = zeros(N,1); for i=1:N Y(i) = 0.0; for j=1:N Y(i) = Y(i) + A(i,j)*x(j); end end initialize space, c 1 N initialize “ for ” loop, c 2 N Scalar assignment, c 3 initialize “ for ” loop, c 2 N c 4 End of loop, return/exit, c 5 End of loop, return/exit, c 5 Total = c 6 N 2 + c 7 N Problem size affects (is, in fact) N Processor speed, processor and language architecture, ie., technology , affect c 6 and c 7 Hence, “ this algorithm of matrix-vector multiply has O(N 2 ) complexity. ” N times N times Time complexity familiar tasks: Time complexity familiar tasks Task Matrix/vector multiply Getting a specific element from a list Dividing a list in half, dividing one halve in half, etc Binary Search Scanning (brute force search) a list Nested for loops (k levels) MergeSort BubbleSort Generate all subsets of a set of data Generate all permutations of a set of data Growth rate O(N 2 ) O(1) O(log 2 N) O(log 2 N) O(N) O(N k ) O(N log 2 N) O(N 2 ) O(2 N ) O(N!)

Related presentations


Other presentations created by lakshmitharun

BrainleeBracelett for blind
09. 03. 2014
0 views

BrainleeBracelett for blind

TimeAndSpaceComplexity
09. 03. 2014
0 views

TimeAndSpaceComplexity

Big-Oh representation
09. 03. 2014
0 views

Big-Oh representation

Big-Oh Notation
22. 02. 2014
0 views

Big-Oh Notation