Aoa

Algorithmic Complexity Outline  Defined 

Big-Oh Notation

Complexity Analysis   

How good is the algorithm? Best case Vs. worst case Storage Vs. computation time

Complexity Complexity Rate at which storage or time grows as a function of the problem size

Asymptotic Analysis 



Describes the inherent complexity of an application, independent of machine and compiler Idea: as problem size grows, the complexity can be described as a simple proportionality to some known function.

Common Notations for Big-O

O(1) 

Constant time or space, independently of what input we give to the algorithm



Examples Access element in an array Retrieve the first element in a list

Code Comparison Put_line(“Enter an integer:”) ; Get(N) ; Sum = 0 ; For I in 1..N do Sum += I ; Put_line(sum) ;

Code Comparison Put_line(“Enter an integer:”) ; Get(N) ; Sum = (N* (N+1)) / 2 ; Put_line(sum) ;

O(N) 

We have to search through all existing elements to find that the element are looking for does not exist

O(N) Examples  Searching for element in a list that does not exist.  Searching through a Binary Tree of size N where a value does not exist.

O(log N) Examples  Example, a full balanced Binary Search Tree  Can eliminate half of the BST every time the search  Any algorithm that eliminates a large portion of the data set at each iteration is generalized into (OlogN)

O(NM)

O(MN)

Big-O

Big-O

Big-O Examples

Big-O Examples

Big-O Simplifications

Big-O Simplifications

Big-O Simplifications

O: Upper Bounding Function Def f(n)= O(g(n)) if ∃ c >0 and n0 > 0 such that 0 ≤ f(n) ≤ cg(n) for all n ≥ n0. Intuition: f(n) “≤ ” g(n) when we ignore constant multiples and small values of n.

O: Upper Bounding Function

O: Upper Bounding Function Def f(n)= O(g(n)) if ∃ c >0 and n0 > 0 such that 0 ≤ f(n) ≤ cg(n) for all n ≥ n0. Intuition: f(n) “≤ ” g(n) when we ignore constant multiples and small values of n.

Ω : Lower Bounding Function Def f(n)= O(g(n)) if ∃ c >0 and n0 > 0 such that 0 ≤ f(n) ≤ cg(n) for all n ≥ n0. Intuition: f(n) “≤ ” g(n) when we ignore constant multiples and small values of n.

Ω : Lower Bounding Function

θ: Tightly Bounding Function Def f(n)= θ(g(n)) if ∃ c1, c2 >0 and n0 > 0 such that 0 ≤ c1g(n) ≤ f(n) ≤ c2 g(n) for all n ≥ n0. Intuition: f(n) “ = ” g(n) when we ignore constant multiples and small values of n.

θ: Tightly Bounding Function

Binary Search Given a sorted array A[1..n] and an item x in A. What is the index of x in A?

.

Max. in an Array

Max. in an Array

Growth Rate

Constant Factors

Big – O Notation

Big – O Notation

Big – O Examples

Big – O and Growth Rate

Big – O Rules

Computing Prefix Averages

Computing Prefix Averages

Computing Prefix Averages

Computing Prefix Averages

Big-Oh

Big-Oh

Big-Oh Calculate

N

3 i ∑ i =1

1

1

2

2N+2

3

4N

4

1

Lines 1 and 4 count for one unit each Line 3: executed N times, each time four units Line 2: (1 for initialization, N+1 for all the tests, N for all the increments) total 2N + 2 total cost: 6N + 4 ⇒ O(N)

Big-Oh Examples N2 / 2 – 3N = O(N2) 1 + 4N = O(N) 7N2 + 10N + 3 = O(N2) = O(N3) log10 N = log2 N / log2 10 = O(log2 N) = O(log N) sin N = O(1); 10 = O(1), 1010 = O(1)

Big-Oh Examples log N + N = O(N) logk N = O(N) for any constant k N = O(2N), but 2N is not O(N) 210N is not O(2N)

Big-Oh Examples Nested for loops

the running time of the statement multiplied by the product of the sizes of all the forloops. O(N2)

Big-Oh Examples Consecutive Statements

These just add O(N) + O(N2) = O(N2)

Big-Oh Examples For large n the largest term dominates so 5n 2+3n+2 is modeled by just n 2.

Big-Oh Examples Big-O notation is a way of comparing functions. Notation unconventional: EG: 3x 3 + 5x 2 – 9 = O (x 3) Doesn’t mean “3x 3 + 5x 2 – 9 equals the function O(x 3)”

Big-Oh Examples Which actually means “3x 3+5x 2 –9 is dominated by x 3” Read as: “3x 3+5x 2 –9 is big-Oh of x 3”

Big-Oh Examples y = 3x 3+5x 2 –9

y=x

3

y=x

2

y=x

Big-Oh Examples Find k so that 3x 3 + 5x 2 – 9 ≤ 5x 3 for x > k Collect terms: 5x 2 ≤ 2x 3 + 9 What k will make 5x 2 ≤ x 3 for x > k ? k=5! So for x > 5, 5x 2 ≤ x 3 ≤ 2x 3 + 9 Solution: C = 5, k = 5 (not unique!)