Asymptotic Analysis CLRS, Sections 3.1 3.2 Asymptotic Complexity Running time of an algorithm as a function of input size n, for large n. Expressed using only the highest-order term in the expression for the exact running time. Describes behavior of function in the limit. Written using Asymptotic Notation. CS 321 - Data Structures 2 Asymptotic Notation , O, , o, Defined for functions over the natural numbers. Ex: f(n) = (n2). Describes how f(n) grows in comparison to n2.

Defines a set of functions; in practice used to compare growth rate of two functions. The notations describe the relationship between the defining function and a defined set of functions. CS 321 - Data Structures 3 O-notation For function g(n), we define O(g(n)), big-O of n, as the set: O(g(n)) = {f(n) : positive constants c and n0, such that n n0,we have 0 f(n) cg(n) } Intuitively: Set of all functions whose rate of growth is the same as or lower than that of g(n). g(n) is an asymptotic upper bound for f(n).

f(n) = (g(n)) f(n) = O(g(n)) (g(n)) O(g(n)) CS 321 - Data Structures 4 -notation For function g(n), we define (g(n)), big-Omega of n, as the set: (g(n)) = {f(n) : positive constants c and n0, such that n n0, we have 0 cg(n) f(n)} Intuitively: Set of all functions whose rate of growth is the same as or higher than that of g(n). g(n) is an asymptotic lower bound for f(n). f(n) = (g(n)) f(n) = (g(n)) (g(n)) (g(n)) CS 321 - Data Structures

5 -notation For function g(n), we define (g(n)), big-Theta of n, as the set: (g(n)) = {f(n) : positive constants c1, c2, and n0, such that n c1g(n) n0, we have 0 f(n) c2g(n)} Intuitively: Set of all functions that have the same rate of growth as g(n). g(n) is an asymptotically tight bound for f(n). CS 321 - Data Structures 6

Relationship Between , O, CS 321 - Data Structures 7 Relationship Between , , O Theorem Theorem :: For For any any two two functions functions g(n) g(n) and and f(n), f(n), f(n) f(n) == (g(n)) (g(n)) iff iff f(n)

f(n) == O(g(n)) O(g(n)) and and f(n) f(n) == (g(n)). (g(n)). (g(n)) = O(g(n)) (g(n)) In practice, asymptotically tight bounds are obtained from asymptotic upper and lower bounds. CS 321 - Data Structures 8 o-notation For a given function g(n), the set little-o: o(g(n)) = {f(n): c > 0, n0 > 0 such that n n0, we have 0 f(n) < cg(n)}. Intuitively: Set of all functions whose rate of growth is lower than that of g(n).

g(n) is an upper bound for f(n)that is not asymptotically tight. CS 321 - Data Structures 9 -notation For a given function g(n), the set little-omega: (g(n)) = {f(n): c > 0, n0 > 0 such that n n0, we have 0 cg(n) < f(n)}. Intuitively: Set of all functions whose rate of growth is higher than that of g(n). g(n) is a lower bound for f(n) that is not asymptotically tight. CS 321 - Data Structures 10 Comparison of Functions

f g f f f f f (n) (n) (n) (n) (n) = = = = = ~ O(g(n))

(g(n)) (g(n)) o(g(n)) (g(n)) a b ~ ~ ~ ~ ~ a a a a a CS 321 - Data Structures b

b = b < b > b 11 Limit Definitions of Asymptotic Notations o-notation (little-o): f(n) becomes insignificant relative to g(n) as n approaches infinity: lim [f(n) / g(n)] = 0 n -notation (little-omega): f(n) becomes arbitrarily large relative to g(n) as n approaches infinity: lim [f(n) / g(n)] = n

CS 321 - Data Structures 12 Limit Definitions of Asymptotic Notations -notation (Big-theta): f(n) relative to g(n)equals a constant, c, which is greater than 0 and less than infinity as n approaches infinity: 0 < lim [f(n) / g(n)] < n CS 321 - Data Structures 13 Limit Definitions of Asymptotic Notations O-notation (Big-o): f(n) O(g(n)) f(n) (g(n))and f(n) o(g(n))

f(n) relative to g(n)equals some value less than infinity as n approaches infinity: lim [f(n) / g(n)] < n -notation (Big-omega): f(n) (g(n)) f(n) (g(n))and f(n) (g(n)) f(n) relative to g(n)equals some value greater than 0 as n approaches infinity: 0 < lim [f(n) / g(n)] n CS 321 - Data Structures 14 Examples Use limit definitions to prove: 10n - 3n O(n2) 3n4 (n3)

n2/2 - 3n (n2) 22n (2n) CS 321 - Data Structures 15 Examples Use limit definitions to prove: 10n - 3n O(n2) Yes! lim [ 10n - 3n / n2 ] = 0 n 3n4 (n3) Yes! lim [ 3n4 / n3 ] = n

n2/2 - 3n (n2) Yes! lim [ n2/2 - 3n / n2 ] = 1/2 n 22n (2n) No! lim [ 22n / 2n ] = n CS 321 - Data Structures 16 Why Do We Care? CS 321 - Data Structures 17

Complexity and Tractability T(n) n 10 20 30 40 50 100 103 104 105 106 n n log n n2 .01ms .03ms .1ms .02ms .09ms

.4ms .03ms .15ms .9ms .04ms .21ms 1.6ms .05ms .28ms 2.5mms .1ms .66ms 10ms 1ms 9.96ms 1ms 10ms 130ms 100ms 100ms 1.66ms 10s 1ms 19.92ms 16.67m n3

n4 1ms 10ms 8ms 160ms 27ms 810ms 64ms 2.56ms 125mms 6.25ms 1ms 100ms 1s 16.67m 16.67m 115.7d 11.57d 3171y 31.71y 3.17107y n10

10s 2.84h 6.83d 121d 3.1y 3171y 3.171013y 3.171023y 3.171033y 3.171043y 2n 1ms 1ms 1s 18m 13d 41013y 3210283y Assuming the microprocessor performs 1 billion ops/s. CS 321 - Data Structures

18 CS 321 - Data Structures 19