TimeComplexity

100 %
0 %
Information about TimeComplexity
Education

Published on March 9, 2014

Author: lakshmitharun

Source: authorstream.com

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!)

Add a comment

Related presentations

Related pages

TimeComplexity - Python Wiki

This page documents the time-complexity (aka "Big O" or "Big Oh") of various operations in current CPython. Other Python implementations (or older or still ...
Read more

TimeComplexity - scribd.com

Chapter 1. Time complexity Use of time complexity makes it easy to estimate the running time of a program. Performing an accurate calculation of a program ...
Read more

Time complexity - Codility

Chapter 3 Time complexity Use of time complexity makes it easy to estimate the running time of a program. Performing an accurate calculation of a program ...
Read more

TimeComplexity (SetCode) - Python Wiki

I don't know about the implementation, but as an exercise, the set union is O(N) w.r.t. len(s)+len(t), and stays the same regardless of the degree of ...
Read more

TimeComplexity - Python Wiki

Search: TimeComplexity TimeComplexity FrontPage RecentChanges FindPage HelpContents TimeComplexity Page Immutable Page Info Attachments More Actions: User
Read more

CocoaDev » Timecomplexity

I am using my own (inconsistent) pseudo code on this page! Also, this is written as a tutorial instead of a definition. An algorithm is the process of ...
Read more

TimeComplexity - YouTube

Time Complexity Analysis for Quick Sort - Algorithm Design & Analysis - Duration: 16:38. GATE ESE PSU'S | IIT JEE | SSC JE/AE Competitive ...
Read more

TimeComplexity - Ace Recommendation Platform - 1

Related Contents; time_complexity_DNA15 alters asymptotic time-complexity. Our results rely on simple asymptotic arguments that should be applicable to a ...
Read more

P vs NP Simply Explained | Time Complexity

I am currently finishing up a summer internship at Google, during which I delved deeply into the realm of applied computer science -- programming, as well ...
Read more

No Slide Title - jagger.berkeley.edu

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 ...
Read more