Algorithm Analysis I

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

1

Kevin Lin, with thanks to many others.

Feedback from the Reading Quiz

Counting operations. Let’s look at an example where N = 6 instead of N = 10000.

Confusing question. What part of dup1 and dup2 required us to specify a range for the number of times an operation was executed?

Parabolas vs. lines.

2

Demo

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.

3

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

4

Orders of Growth

5

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

Asymptotic Analysis and Case Analysis

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

6

Q

For a very large array, is it possible for dup1 to execute only 2 less-than (<) operations?

7

Duplicate Finding

Our goal is to somehow characterize the runtimes of the functions below.

• Characterization should be simple and mathematically rigorous.
• Characterization should demonstrate superiority of dup2 over dup1.

8

Worst Case Order of Growth

9

Simplification 1: Consider Only the Worst Case

Provides a runtime guarantee for any input of size N.

We often only care about worst case, but there are many exceptions.

10

public static boolean dup1(int[] A) {

for (int i = 0; i < A.length; i += 1) {

for (int j = i + 1; j < A.length; j += 1) {

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

return true;

}

}

}

return false;

}

Identifying Orders of Growth

Consider the algorithm step counts below.

What do you expect will be the order of growth of the runtime for the algorithm?

​

1. N [linear]
2. N² [quadratic]
3. N³ [cubic]
4. N⁶ [sextic]

11

Q

What do you expect will be the order of growth?

12

Simplification 2: Restrict Attention to One Operation

Pick some representative operation to act as a proxy for the overall runtime.

Good choices:

• Less-than (<)
• Increment (+= 1)
• Equality (==)
• Array accesses

Poor choices: assignment of i = 0 or j = i + 1.

We call our choice the cost model.

13

Simplification 3: Eliminate Lower-Order Terms

Ignore lower-order terms.

14

public static boolean dup1(int[] A) {

for (int i = 0; i < A.length; i += 1) {

for (int j = i + 1; j < A.length; j += 1) {

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

return true;

}

}

}

return false;

}

Simplification 4: Eliminate Multiplicative Constants

Ignore multiplicative constants.

We already threw away the meaningful constant when we chose a single proxy operation.

15

public static boolean dup1(int[] A) {

for (int i = 0; i < A.length; i += 1) {

for (int j = i + 1; j < A.length; j += 1) {

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

return true;

}

}

}

return false;

}

Simplification Summary

1. Only consider the worst case.
2. Pick a representative operation (cost model).
3. Ignore lower order terms.
4. Ignore multiplicative constants.

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

16

Order of growth

Your Turn: Worst Case Order of Growth for dup2

• Only consider the worst case.
• Pick a representative operation (cost model).
• Ignore lower order terms.
• Ignore multiplicative constants.

“The worst case order of growth of the runtime for dup2 is …”

17

Order of growth

Q

Simplified Modeling Process

Rather than building the entire table, we can instead:

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

​

Let’s redo our analysis of dup1 with this new process.

This time, we’ll show all our work.

18

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

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

19

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².”

20

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.

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

21

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

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.

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

22

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

Order of Growth Exercise

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

In other words, what is the order of growth of each function?

23

Q

Big-Theta Notation

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

24

Big-Theta Definition

​

​

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

​

​

for all values of N greater than some N₀.

25

“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₀.

26

Q

Demo

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.

27

Big-O Definition

​

​

means there exists a positive constant k₂ such that

​

​

for all values of N greater than some N₀.

28

“Very large N”

Big-Omega Definition

​

​

means there exists a positive constant k₁ such that

​

​

for all values of N greater than some N₀.

29

“Very large 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.

“The overall order of growth of the runtime for dup1 is …”

30

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 and Case Analysis

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

31

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

32

Q

Demo