Algorithm Analysis

Runtime analysis as a process: comprehending programs, modeling the number of steps, and formulating an answer.

1

Kevin Lin, with thanks to many others.

Runtime Analysis Process

Comprehending. Understanding the implementation details of a program.

Modeling. Counting the number of steps in terms of N, the size of the input.

Case Analysis. How certain conditions affect the program execution.

Asymptotic Analysis. Describing what happens for very large N, as N→∞.

Formalizing. Summarizing the final result in precise English or math notation.

2

boolean dup1(int[] A)

Consider every pair

Array contains a duplicate at front

Array contains no duplicate items

Constant time

Quadratic time

Θ(1)

Θ(N²)

Overall Asymptotic Runtime Bound

Worst case

Best case

Asymptotic Analysis

What happens for very large N, as N→∞.

​

Simulating billions of particles.

Social network with billions of users.

Logging billions of transactions.

Encoding billions of bytes of video data.

​

Linear-time algorithms scale better than quadratic-time algorithms (parabolas).

3

Algorithms (Robert Sedgewick, Kevin Wayne/Princeton)

Orders of Growth

4

Algorithm Design (Jon Kleinberg, Éva Tardos/Pearson Education)

Asymptotic Analysis vs. Case Analysis

For a very large array with billions of elements (asymptotic analysis), how is it possible for dup1 to execute only 2 less-than (<) operations?

5

Q

Asymptotic Analysis vs. Case Analysis

First two items are the duplicates. That makes sense for large inputs.

• Contents of the array.
• Even when working with a very large input, all we’ve said is we have a large array.

​

Case analysis coexists with asymptotic analysis.

​

In the case of 0 items in the array, there’s only one less than. That seems fast.

• Why is this thinking wrong for the problem?
• Asymptotic analysis cares about big inputs: large N.

6

A

Runtime Analysis Process

Comprehending. Understanding the implementation details of a program.

Modeling. Counting the number of steps in terms of N, the size of the input.

Case Analysis. How certain conditions affect the program execution.

Asymptotic Analysis. Describing what happens for very large N, as N→∞.

Formalizing. Summarizing the final result in precise English or math notation.

7

boolean dup1(int[] A)

Consider every pair

Array contains a duplicate at front

Array contains no duplicate items

Constant time

Quadratic time

Θ(1)

Θ(N²)

Overall Asymptotic Runtime Bound

Worst case

Best case

Simplified Modeling Process

Rather than building the entire table of operation counts, we can instead:

1. Choose our cost model (representative operation).
2. Figure out the order of growth for the count of the cost model by either:
• Making an exact count and then discarding the unnecessary pieces.
• Or, using intuition/inspection to determine order of growth. (Needs practice!)

​

Let’s redo our analysis of dup1 with this Simplified Modeling Process.

This time, we’ll show all our work.

8

Worst Case Order of Growth: Exact Count of == Operations

“The worst case order of growth of the runtime for dup1 is N².”

9

int N = A.length; // N == 6

for (int i = 0; i < N; i += 1)

for (int j = i + 1; j < N; j += 1)

if (A[i] == A[j])

return true;

return false;

0

1

2

3

4

5

0 1 2 3 4 5

i

j

Worst Case Order of Growth: Geometric Argument

“The worst case order of growth of the runtime for dup1 is N².”

10

int N = A.length; // N == 6

for (int i = 0; i < N; i += 1)

for (int j = i + 1; j < N; j += 1)

if (A[i] == A[j])

return true;

return false;

0

1

2

3

4

5

0 1 2 3 4 5

i

j

Area of right triangle of side length N - 1.

Order of growth of area is N².

Runtime Analysis Process

Comprehending. Understanding the implementation details of a program.

Modeling. Counting the number of steps in terms of N, the size of the input.

Case Analysis. How certain conditions affect the program execution.

Asymptotic Analysis. Describing what happens for very large N, as N→∞.

Formalizing. Summarizing the final result in precise English or math notation.

11

boolean dup1(int[] A)

Consider every pair

Array contains a duplicate at front

Array contains no duplicate items

Constant time

Quadratic time

Θ(1)

Θ(N²)

Overall Asymptotic Runtime Bound

Worst case

Best case

“The worst case order of growth of the runtime for dup1 is N².”

Order of Growth Exercise

What is the order of growth of each function?

(Informally, what is the shape of each function for very large N?)

​

12

Q

Big-Theta Notation

Suppose we have a function R(N) with order of growth f(N). In Big-Theta, we write this as:

13

Big-Theta Definition

​

​

means there exist positive constants k₁ and k₂ such that

​

​

for all values of N greater than some N₀.

14

“Very large N”

Big-Theta Challenge

Find a simple f(N) and corresponding k₁ and k₂.

​

​

means there exist positive constants k₁ and k₂ such that

​

​

for all values of N greater than some N₀.

15

Q

Big-O Notation

Whereas Big-Theta can informally be thought of as something like “equals”, Big-O can be thought of as “less than or equal”.

All of the following are true.

16

Big-O Definition

​

​

means there exists a positive constant k₂ such that

​

​

for all values of N greater than some N₀.

17

“Very large N”

Big-Omega Definition

​

​

means there exists a positive constant k₁ such that

​

​

for all values of N greater than some N₀.

18

“Very large N”

Overall Asymptotic Runtime Bound for dup1

Give an overall asymptotic runtime bound for R as a combination of Θ, O, and/or Ω notation. Take into account both the best and the worst case runtimes (R_best and R_worst). N is the length of array.

​

​

Then, give a few other valid runtime bounds for R_best , R_worst , and R using asymptotic notation.

19

Q

Tight Asymptotic Runtime Bounds for dup1

Best case: Ω(1) and O(1), therefore Θ(1).

Worst case: Ω(N²) and O(N²), therefore Θ(N²).

Overall: Ω(1) and O(N²).

Because the Ω and O bounds do not agree, Θ bound does not exist.

20

A

Valid but Less-Descriptive Runtime Bounds for dup1

Best case: Ω(1) and O(1), therefore Θ(1).

• O(N⁴)
• Lowest order of growth is constant.

Worst case: Ω(N²) and O(N²), therefore Θ(N²).

• O(N⁴)

Overall: Ω(1) and O(N²).

Because the Ω and O bounds do not agree, Θ bound does not exist.

• O(N⁴)

21

A

Mystery

Give a tight asymptotic runtime bound for mystery as a function of N, the length of the array, in the best case, worst case, and overall.

22

Q

boolean mystery(int[] a, int target) {

int N = a.length;

for (int i = 0; i < N; i += 1)

if (a[i] == target)

return true;

return false;

}

Mystery: Big-Ω, Big-O, and Big-Θ

Best case: First element in array is the target.

• Omega(1), O(1), Theta(1)

Worst case: Target is the last item in array.

• O(N), O(N²), Omega(N), Theta(N)
• Can you write Omega(N - 1)? Yes, but it’s not a “simple” function.

Overall:

• No big-theta bound.
• O(N), Omega(1)

23

A