Time Complexity

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

Total = c1N+c2N+N(c3+c2N+N(c4+c5)+c5) = (c2+c4+c5)N2 + (c1+c2+c3+c5)N = c6N2 + c7N

N times

Y = zeros(N,1); initialize space, c1N initialize “for” loop, c2N for i=1:N Scalar assignment, c3 Y(i) = 0.0; initialize “for” loop, c2N for j=1:N c4 Y(i) = Y(i) + A(i,j)*x(j); End of loop, return/exit, c5 end End of loop, return/exit, c5 end

N times

(3 accesses, 1 add, 1 multiply)

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 Given two functions, f and g, say that “f is of order g” if – there is a constant c, and – a value x0

such that

f ( x ) ≤ c ⋅ g ( x ) for all x > x0

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 f = O( g ) to mean “f is of order g”. Sometimes write f ( x ) arguments are labled.

= O( g ( x ) ) to remind us what the

Not equality,but “belongs to a class” Recall that f ( n ) = O( g ( n ) ) means that – there is a constant c, and – a value n0

such that f ( n ) ≤ c ⋅ g ( n ) for all n > n0 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

3n = O( n ) ,

( )

3n = O n 2 ,

(

3n = O n 3 ⋅ log n

)

Big O: Examples Example:

Note:

f ( n ) = 31 g ( n) = 1 for all n > 0, 31 ≤ 31 f ( n ) 31⋅ g (n)

For all n, f is bounded above by 31g Write or

f ( n ) = O( g ( n ) ) 31 = O(1)

Big O: Examples Example:

f ( n ) = 4n 2 + 7 n + 12 g ( n) = n 2

2 2 for n > 8 , 4 n + 7 n + 12 < 5 n Note:

f ( n) For large enough n f is bounded above by 5g Write f ( n ) = O( g ( n ) ) f = O( g ) or 2 2 4 n + 7 n + 12 = O n or

( )

5 g ( n) 1200

1000

800

600

400

200

0

0

5

10

15

Big O: Relationships Suppose f1 and f2 satisfy: There is a value n0

f1 ( n ) ≤ f 2 ( n ) for all n > n0 Then f1 ( n ) + f 2 ( n ) ≤ 2 f 2 ( n ) for all n > n0 Hence

f1 + f 2 = O( f 2 )

Example 3:

27 log( n ) + 19 + n = O( n ) f1 ( n )

f 2 ( n)

Generalization: f1 = O( f 2 ) ⇒

f1 + f 2 = O( f 2 )

Big O: Relationships Suppose positive functions f1, f2, g1, g2, satisfy

f1 = O( g1 ) and Then f1 ⋅ f 2 = O( g1 ⋅ g 2 )

f 2 = O( g 2 )

Why? There exist c1, c2, n1, n2 such that

f i ( n ) ≤ ci ⋅ g i ( n ) for all n > ni

Take c0=c1c2, n0=max(n1,n2). Multiply to give

f1 ( n ) f ( n ) 2 ≤ c0 ⋅ g1 ( n ) g 2 ( n ) for all n > n0

Example:

(12n

2

)

( )

+ 2 log n ( 27 log( n ) + 19 + n ) = O n 3 f 2 ( n) f1 ( n )

Asymptotic: Relationships Obviously, for any positive function g

g = O( g ) Let β be a positive constant. Then β ⋅ g = O( g ) as well.

( )

Example 4: 13n = O n 3

3

Message: Bounding of growth rate. If n doubles, then the bound grows by 8. Example 5:

log n = O( log n ) 512

N times

Y = zeros(N,1); initialize space, c1N initialize “for” loop, c2N for i=1:N Scalar assignment, c3 Y(i) = 0.0; initialize “for” loop, c2N for j=1:N c4 Y(i) = Y(i) + A(i,j)*x(j); End of loop, return/exit, c5 end End of loop, return/exit, c5 end

N times

Example: N-by-N matrix, N-by-1 vector, multiply

Total = c6N2 + c7N •Problem size affects (is, in fact) N •Processor speed, processor and language architecture, ie., technology, affect c6 and c7 Hence, “this algorithm of matrix-vector multiply has O(N2) complexity.”

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(N2) O(1) O(log2N) O(log2N) O(N) O(Nk) O(N log2N) O(N2) O(2N) O(N!)