Asymptotics 3

1

Lecture 15

CS61B, Fall 2024 @ UC Berkeley

Slides Credit: Josh Hug

Intuitive Definitions of Functions

Summations

Lecture 13, CS61B, Spring 2025

Summations

Analyzing Programs

• Nested For Loops
• Amortized Analysis
• Recursive Analysis

Mergesort

3

Summations and Recursive Functions

Sometimes, it's not easy to get an explicit runtime function, but it is possible to Theta bound the function. Often, you can reduce a runtime function to one of:

• A summation Σ_{i=1 to N} f(i) = f(1) + f(2) + f(3) + … + f(N)
• A recursively defined function

​

Triangle Summation

Example: f(N) = Σ_{i=1 to N} i = 1 + 2 + 3 + 4 + … + N ∈ Θ(N²)

​

Approach 1: Algebra

​

5

f(N) = (N - 1) + (N - 2) + (N - 3) + … + 3 + 2 + 1 +N

2f(N) = N + N + … + N (N-1 copies) + N + N

∴ f(N) = N(N + 1)/2

f(N) = 1 + 2 + 3 + … + (N - 3) + (N - 2) + (N - 1) + N

Triangle Summation

Example: f(N) = Σ_{i=1 to N} i = 1 + 2 + 3 + 4 + … + N ∈ Θ(N²)

​

Approach 2: Geometry

The sum is given by the area of this step-wise triangle,

which is approximately a triangle.

Area of triangle is base * height/2 = N * N/2 ∈ Θ(N²)

​

6

Summation of Halves

What is 1 + ½ + ¼ + ⅛ + …

7

Summation of Halves

What is 1 + ½ + ¼ + ⅛ + …

2

Algebraic proof:

Let x = 1 + ½ + ¼ + ⅛ + …

Then 2x = 2 + 1 + ½ + ¼ + ⅛ + …

So 2x - x = 2 + 0…

So x = 2

​

8

Summation of Halves

What is 1 + ½ + ¼ + ⅛ + …

2

Geometric proof: Each step moves halfway to the "2", so you always approach, but never hit, 2.

​

9

Summation of Powers of 2

What is 1 + ½ + ¼ + ⅛ + …

2

If you multiply everything in the below by 2^N, you get the sequence

2^N+2^N-1+...+2¹+ 1 + ½ +¼ + ⅛ +... = 2*2^N

​

​

​

​

​

So 1+2+4+...+2^N = 2*2^N-1

10

1

Infinite Summation

For any r < 1, Σ_{i=1 to ∞} rⁱ = 1+r+r²+r³+... the sum can be evaluated:

​

Let x = 1+ r+r²+r³...

Then r*x = r+r²+r³…

So x-r*x = 1

x = 1/(1-r)

​

(Note: If r≥1, then the sum diverges to infinity. Formally, the power series has a radius of convergence of 1)

11

Exponential Summation

Show that for any r > 1, Σ_{i=0 to N} rⁱ = 1+r+r²+r³+...+r^N ∈ Θ(r^N) by showing:

​

Σ_{i=0 to N} rⁱ = 1+r+r²+r³+...+r^N ∈ Ω(r^N)

​

​

​

Σ_{i=0 to N} rⁱ = 1+r+r²+r³+...+r^N ∈ O(r^N)

12

Exponential Summation

Show that for any r > 1, Σ_{i=0 to N} rⁱ = 1+r+r²+r³+...+r^N ∈ Θ(r^N) by showing:

​

Σ_{i=0 to N} rⁱ = 1+r+r²+r³+...+r^N ∈ Ω(r^N)

The sum is greater than the last term, so Σ_{i=1 to N} rⁱ > r^N ≥ 1*(r^N)

​

​

Σ_{i=0 to N} rⁱ = 1+r+r²+r³+...+r^N ∈ O(r^N)

The sum is the same as r^N*(1+1/r+(1/r)²+...+(1/r)^N) = r^N*(Σ_{i=1 to N} (1/r)ⁱ)

Note that Σ_{i=1 to N} (1/r)ⁱ < Σ_{i=1 to ∞} (1/r)ⁱ = 1/(1-1/r), because if r>1, then 1/r < 1.

So the sum is ≤r^N*(1/(1-1/r)), where (1/(1-1/r)) is a constant

13

Repeat After Me...

There is no magic shortcut for asymptotic analysis problems

• Function analysis often requires careful thought.
• CS70 and especially CS170 will cover this in much more detail.
• This is not a math class, though we’ll expect you to know these:
• 1 + 2 + 3 + … + N = N(N+1)/2 = Θ(N²)
• 1^k+2^k+3^k+ … + N^k (k >=0) = Θ(N^k+1)
• 1 + 2 + 4 + 8 + … + 2^N = 2*2^N - 1 = Θ(2^N)
• k⁰+k¹+k²+ … + k^N (k > 1) = Θ(k^N)

← Sum of First Natural Numbers (Link)

← Sum of First Powers of 2 (Link)

​

← Generalization of ^

← Generalization of ^

​

Repeat After Me...

There is no magic shortcut for asymptotic analysis problems

• Function analysis often requires careful thought.
• CS70 and especially CS170 will cover this in much more detail.
• This is not a math class, though we’ll expect you to know these:
• 1 + 2 + 3 + … + N = N(N+1)/2 = Θ(N²)
• 1^k+2^k+3^k+ … + N^k (k >=0) = Θ(N^k+1)
• 1 + 2 + 4 + 8 + … + N = 2*N - 1 = Θ(N)
• k⁰+k¹+k²+ … + N (k > 1) = Θ(N)

← Sum of First Natural Numbers (Link)

← Alternate form of sum of powers

​

← Generalization of ^

← Generalization of ^

​

Repeat After Me...

There is no magic shortcut for asymptotic analysis problems

• Function analysis often requires careful thought.
• CS70 and especially CS170 will cover this in much more detail.
• This is not a math class, though we’ll expect you to know these:
• Σ_{i=1 to N} i = N(N+1)/2 = Θ(N²)
• Σ_{i=1 to N} i^k (k >=0) = Θ(N^k+1)
• Σ_{i=0 to N} 2ⁱ = 2*2^N - 1 = Θ(2^N)
• Σ_{i=0 to N} kⁱ (k > 1) = Θ(k^N)

← Sum of First Natural Numbers (Link)

← Sum of First Powers of 2 (Link)

​

← Generalization of ^

← Generalization of ^

​

Repeat After Me...

There is no magic shortcut for asymptotic analysis problems

• Function analysis often requires careful thought.
• CS70 and especially CS170 will cover this in much more detail.
• This is not a math class, though we’ll expect you to know these:
• 1^k+2^k+3^k+ … + N^k (k ≥ 0) = Θ(N^k+1)
• k⁰+k¹+k²+ … + k^N (k > 1) = Θ(k^N)
• Strategies:
• Find exact sum.
• Write out examples.
• Draw pictures.

QR decomposition runtime, from “Numerical Linear Algebra” by Trefethen.

Generalizing the two cases you need to know (Out of Scope)

• 1^k+2^k+3^k+ … + N^k (k >=0) = Θ(N^k+1)
• k⁰+k¹+k²+ … + k^N (k > 1) = Θ(k^N)

Σ_{i=0 to N} f(i) (f continuous, increasing)

​

​

​

Generalizing the two cases you need to know (Out of Scope)

• 1^k+2^k+3^k+ … + N^k (k >=0) = Θ(N^k+1)
• k⁰+k¹+k²+ … + k^N (k > 1) = Θ(k^N)

Σ_{i=0 to N} f(i) ∈ Θ(∫₀^N f(x)) (for most functions)

Some shortcuts exist

But they tend to be limited in scope

​

​

​

Summary (No pun intended)

Summations are difficult to evaluate

• Even minor changes to the function can yield much harder problems
• Though you can solve a decent chunk of problems by using calculus

In practice, you won't be working with the raw math and proofs, because that adds too much complexity.

Fortunately, you don't have to!

Just as in programming, we can abstract the

formal math, and use the tools we proved work.

Let's discuss how to actually use

these tools to compute the runtime of programs.

Nested For Loops

Lecture 15, CS61B, Fall 2024

Summations

Analyzing Programs

• Nested For Loops
• Amortized Analysis
• Recursive Analysis

Mergesort

Measuring a Program's Performance

Expressing a program's efficiency boils down to two main steps:

1. Define some metric by which the program's efficiency will be evaluated, and measure the program's efficiency according to that metric.
• Since we'll use a Theta bound in step 2, we can ignore constant factors in this step, which is useful in simplifying runtimes
2. Classify the resulting function in a Theta class.
• Often requires summations or special tricks to get to a form we can actually solve.

22

Loops Example:

Find a simple f(N) such that the runtime R(N) ∈ Θ(f(N)). By simple, we mean there should be no unnecessary multiplicative constants or additive terms.

​

​

​

​

​

​

​

​

1. 1
2. log N
3. N

​

D. N log N

E. N²

F. Other

public static void printParty(int N) {

for (int i = 1; i <= N; i = i * 2) {

for (int j = 0; j < i; j += 1) {

System.out.println("hello");

int ZUG = 1 + 1;

}

}

}

​

Note that there’s only one case for this code and thus there’s no distinction between “worst case” and otherwise.

Loops Example

Find a simple f(N) such that the runtime R(N) ∈ Θ(f(N)).

Units of work C(N):

0

1

2

3

4

5

0 1 2 3 4 5

j

i

N

public static void printParty(int N) {

for (int i = 1; i <= N; i = i * 2) {

for (int j = 0; j < i; j += 1) {

//1 unit of work

} } }

C(N)

Loops Example

Find a simple f(N) such that the runtime R(N) ∈ Θ(f(N)).

Units of work C(N):

0

1

2

3

4

5

0 1 2 3 4 5

Work

i

N

public static void printParty(int N) {

for (int i = 1; i <= N; i = i * 2) {

//i units of work

}

}

C(N)

Loops Example

Find a simple f(N) such that the runtime R(N) ∈ Θ(f(N)).

Units of work C(N):

0

1

2

3

4

5

0 1 2 3 4 5

i

N

C(N)

public static void printParty(int N) {

for (int i = 1; i <= N; i = i * 2) {

//i units of work

}

}

​

Work

Loops Example

Find a simple f(N) such that the runtime R(N) ∈ Θ(f(N)).

Units of work C(N):

0

1

2

3

4

5

0 1 2 3 4 5

i

N

public static void printParty(int N) {

for (int i = 1; i <= N; i = i * 2) {

//i units of work

}

}

​

C(N)

Work

Loops Example

Find a simple f(N) such that the runtime R(N) ∈ Θ(f(N)).

Units of work C(N):

0

1

2

3

4

5

0 1 2 3 4 5

i

N

public static void printParty(int N) {

for (int i = 1; i <= N; i = i * 2) {

//i units of work

}

}

​

C(N)

N=3 doesn't do anything extra

Work

Loops Example

Find a simple f(N) such that the runtime R(N) ∈ Θ(f(N)).

Units of work C(N):

0

1

2

3

4

5

0 1 2 3 4 5

i

N

public static void printParty(int N) {

for (int i = 1; i <= N; i = i * 2) {

//i units of work

}

}

​

C(N)

Work

Loops Example

Find a simple f(N) such that the runtime R(N) ∈ Θ(f(N)).

Units of work C(N):

0

1

2

3

4

5

0 1 2 3 4 5

i

N

public static void printParty(int N) {

for (int i = 1; i <= N; i = i * 2) {

//i units of work

}

}

​

C(N)

Work

N=4,5,6,7 all print 7 times

Loops Example

Find a simple f(N) such that the runtime R(N) ∈ Θ(f(N)).

Units of work C(N):

0

1

2

3

4

5

0 1 2 3 4 5

i

N

public static void printParty(int N) {

for (int i = 1; i <= N; i = i * 2) {

//i units of work

}

}

​

C(N)

Work

N=4,5,6,7 all print 7 times

Loops Example

Find a simple f(N) such that the runtime R(N) ∈ Θ(f(N)).

Units of work C(N):

0

1

2

3

4

5

0 1 2 3 4 5

i

N

public static void printParty(int N) {

for (int i = 1; i <= N; i = i * 2) {

//i units of work

}

}

​

C(N)

Work

These N all print 15 times

Loops Example

Find a simple f(N) such that the runtime R(N) ∈ Θ(f(N)).

Units of work C(N):

0

1

2

3

4

5

0 1 2 3 4 5

i

N

public static void printParty(int N) {

for (int i = 1; i <= N; i = i * 2) {

//i units of work

}

}

​

C(N)

Work

C(N) = 1 + 2 + 4 + … + N, if N is a power of 2

Loops Example

We’re trying to find the order of growth of C(N):

Units of work C(N):

N

C(N)

C(N) = 1 + 2 + 4 + … + N, if N is a power of 2

Loops Example:

Find a simple f(N) such that the runtime R(N) ∈ Θ(f(N)).

Cost model C(N):

D. N log N

E. N²

F. Other

1. 1
2. log N
3. N

public static void printParty(int N) {

for (int i = 1; i<=N; i = i * 2) {

for (int j = 0; j < i; j += 1) {

System.out.println("hello");

int ZUG = 1 + 1;

N

C(N)

C(N) = 1 + 2 + 4 + … + N, if N is a power of 2

Loops Example 2 [attempt #3] (no yellkey)

Find a simple f(N) such that the runtime R(N) ∈ Θ(f(N)).

The "peaks" of C(N) are when N = 2^k.

Total = 1+2+4+...+N ∈ Θ(N)

The "troughs" of C(N) are when N = 2^k-1.

Total = 1+2+4+...+(N+1)/2 ∈ Θ((N+1)/2)

∈ Θ(N)

• 1
• log N
• N

D. N log N

E. N²

F. Something else

Amortized Analysis

Lecture 15, CS61B, Fall 2024

Summations

Analyzing Programs

• Nested For Loops
• Amortized Analysis
• Recursive Analysis

Mergesort

Surely no function does this, right?

Let's play with this function a bit

public static void printParty(int n) {

for (int i = 1; i <= n; i = i * 2) {

//i units of work

}

}

​

Surely no function does this, right?

Add Θ(N) work: Total runtime is still Θ(N)

public static void printParty(int n) {

for (int i = 1; i <= n; i = i * 2) {

//i units of work

}

for (int i = 1; i <= n; i++) {

//1 unit of work

}

}

​

Surely no function does this, right?

Combine the for loops. No asymptotic change in work done

public static void printParty(int n) {

for (int i = 1; i <= n; i++) {

//1 unit of work

if(i is a power of 2) {

//i units of work

}

}

}

​

Surely no function does this, right?

Put things in separate functions. Changes an O(1) thing to more O(1) things, so no runtime difference.

public static void printParty(int n) {

for (int i = 1; i <= n; i++) {

foo();

} }

public static void foo() {

if(i is a power of 2) {

bar(i);

}

// 1 unit of work

}

public static void bar(i) {

//i units of work

}

Surely no function does this, right?

Rename functions and define what we do in the commented code. No change in runtime.

public void addMany(int n) {

for (int i = 0; i < n; i++) {

addLast(1);

} }

public void addLast(int value) {

if(this.length == arr.length) {

resize(this.length * 2);

} //Happens every time length is 2^k

//addLast code takes 1 unit of work

}

public void resize(int i) {

//resizing takes i units of work

}

Why geometric resizing is faster

When we discussed ArrayLists, we handwaved why geometric resizing is better than linear resizing. Now that we know asymptotics, we can finally prove this.

After N addLasts, runtime is Θ(N²)

After N addLasts,

runtime is Θ(N)

​

public void addLast(int x) {

if (size == items.length) {

resize(size + RFACTOR);

}

items[size] = x;

size += 1;

}

public void addLast(int x) {

if (size == items.length) {

resize(size * RFACTOR);

}

items[size] = x;

size += 1;

}

Why geometric resizing is faster

Even though the worst-case resize is still Θ(N), they happen so infrequently with geometric resizing that we get Θ(1) runtime on average regardless of how we order List operations.

Each addLast takes on average Θ(N) time

Each addLast takes on average Θ(1) time

​

public void addLast(int x) {

if (size == items.length) {

resize(size + RFACTOR);

}

items[size] = x;

size += 1;

}

public void addLast(int x) {

if (size == items.length) {

resize(size * RFACTOR);

}

items[size] = x;

size += 1;

}

Amortized Runtime

This is known as Amortized Runtime

• Any single operation may take longer, but if we use it over many operations, we're guaranteed to have a better average performance
• So amortized runtime gives a better estimate of how much time it takes to use something in practice

addLast is Θ(1) amortized

​

public void addLast(int x) {

if (size == items.length) {

resize(size * RFACTOR);

}

items[size] = x;

size += 1;

}

Recursive Analysis

Lecture 15, CS61B, Fall 2024

Summations

Analyzing Programs

• Nested For Loops
• Amortized Analysis
• Recursive Analysis

Mergesort

Recursion, Approach 1: Intuitive

Find a simple f(N) such that the runtime R(N) ∈ Θ(f(N)).

Using your intuition, give the order of growth of the runtime of this code as a function of N?

1. 1
2. log N
3. N
4. N²
5. 2^N

public static int f3(int n) {

if (n <= 1)

return 1;

return f3(n-1) + f3(n-1);

}

​

Recursion, Approach 1: Intuitive

Find a simple f(N) such that the runtime R(N) ∈ Θ(f(N)).

Using your intuition, give the order of growth of the runtime of this code as a function of N?

• 1
• log N
• N
• N²
• 2^N

5

public static int f3(int n) {

if (n <= 1)

return 1;

return f3(n-1) + f3(n-1);

}

​

2^N: Every time we increase N by 1, we double the work!

Recursion, Approach 2: Exact Counting

Find a simple f(N) such that the runtime R(N) ∈ Θ(f(N)).

Another approach: Count number of calls to f3, given by C(N).

Each function call does a constant amount of work (not counting recursive calls), so C(N) ∈ Θ(R(N))

• C(1) = 1
• C(2) = 1 + 2
• C(3) = 1 + 2 + 4

​

public static int f3(int n) {

if (n <= 1)

return 1;

return f3(n-1) + f3(n-1);

}

​

Recursion, Approach 2: Exact Counting: http://yellkey.com/happy

Find a simple f(N) such that the runtime R(N) ∈ Θ(f(N)).

Another approach: Count number of calls to f3, given by C(N).

• C(3) = 1 + 2 + 4
• C(N) = 1 + 2 + 4 + … + ???

What is the final term of the sum?

1. N
2. 2^N
3. 2^N-1

public static int f3(int n) {

if (n <= 1)

return 1;

return f3(n-1) + f3(n-1);

}

​

D. 2^N-1

E. 2^N-1-1

Recursion, Approach 2: Exact Counting

Find a simple f(N) such that the runtime R(N) ∈ Θ(f(N)).

Another approach: Count number of calls to f3, given by C(N).

• C(3) = 1 + 2 + 4
• C(N) = 1 + 2 + 4 + … + ???

What is the final term of the sum?

public static int f3(int n) {

if (n <= 1)

return 1;

return f3(n-1) + f3(n-1);

}

​

D. 2^N-1

​

Recursion, Approach 2: Exact Counting

Find a simple f(N) such that the runtime R(N) ∈ Θ(f(N)).

Another approach: Count number of calls to f3, given by C(N).

• C(N) = 1 + 2 + 4 + … + 2^N-1

​

Give a simple expression for C(N).

​

public static int f3(int n) {

if (n <= 1)

return 1;

return f3(n-1) + f3(n-1);

}

​

Recursion, Approach 2: Exact Counting

Find a simple f(N) such that the runtime R(N) ∈ Θ(f(N)).

Another approach: Count number of calls to f3, given by C(N).

• C(N) = 1 + 2 + 4 + … + 2^N-1

​

Give a simple expression for C(N).

• C(N) = 2(2^N-1) - 1
• C(N) = 2^N-1

​

public static int f3(int n) {

if (n <= 1)

return 1;

return f3(n-1) + f3(n-1);

}

​

Recursion, Approach 2: Exact Counting

Find a simple f(N) such that the runtime R(N) ∈ Θ(f(N)).

Another approach: Count number of calls to f3, given by C(N).

• C(N) = 1 + 2 + 4 + … + 2^N-1
• Solving, we get C(N) = 2^N - 1

​

Since work during each call is constant:

• R(N) = Θ(2^N)

public static int f3(int n) {

if (n <= 1)

return 1;

return f3(n-1) + f3(n-1);

}

​

Recursion, A minor change

Find a simple f(N) such that the runtime R(N) ∈ Θ(f(N)).

What happens if we make this tiny change?

• C(0) = 1
• C(1) = 1
• C(2) = 1+1+1
• C(3) = 1+1+2+1
• ?????

Give a simple expression for C(N).

​

public static int fib(int n) {

if (n <= 1)

return 1;

return fib(n-1) + fib(n-2);

}

​

2

1

0

4

3

2

1

1

0

Recursion, A minor change (Out of Scope)

Find a simple f(N) such that the runtime R(N) ∈ Θ(f(N)).

For this one, we'll have to be a bit more creative:

• fib(n) returns the nth Fibonacci number F_n
• In the tree on the right, there are F_n yellow nodes
• Why? Each leaf adds 1 to the final sum
• In the tree on the right, there are F_n-1 green nodes
• Why? To sum k 1s, we do k-1 +s

C(N) = # yellow + # green = 2(F_N)-1 = Θ(F_N)

​

public static int fib(int n) {

if (n <= 1)

return 1;

return fib(n-1) + fib(n-2);

}

​

2

1

0

4

3

2

1

1

0

Recursion, A minor change (Out of Scope)

Find a simple f(N) such that the runtime R(N) ∈ Θ(f(N)).

C(N) = # yellow + # green = 2(F_N)-1 = Θ(F_N)

If you do enough math, you find that F_N∈ Θ(φ^N)

Where φ = (1+sqrt(5))/2 ≈ 1.618

Each function call does 1 unit of work

So R(N) = Θ(1.618^N)

In conclusion: There is no Magic Shortcut for

Asymptotic Analysis

public static int fib(int n) {

if (n <= 1)

return 1;

return fib(n-1) + fib(n-2);

}

​

2

1

0

4

3

2

1

1

0

Recursion, Approach 3: Recurrence Relations (Out of Scope for 61B)

​

Find a simple f(N) such that the runtime R(N) ∈ Θ(f(N)).

Third approach: Count number of calls to f3, given by a “recurrence relation” for C(N).

• C(1) = 1
• C(N) =

2C(N-1) + 1

public static int f3(int n) {

if (n <= 1)

return 1;

return f3(n-1) + f3(n-1)

}

​

Recursion, Approach 3: Recurrence Relations (Out of Scope for 61B)

Find a simple f(N) such that the runtime R(N) ∈ Θ(f(N)).

Third approach: Count number of calls to f3, given by a “recurrence relation” for C(N).

• C(1) = 1
• C(N) =

public static int f3(int n) {

if (n <= 1)

return 1;

return f3(n-1) + f3(n-1)

}

​

More technical to solve. Won’t do this in our course. See next slide for solution.

2C(N-1) + 1

Recursion, Approach 3: Recurrence Relations (Out of Scope for 61B)

Find a simple f(N) such that the runtime R(N) ∈ Θ(f(N)).

Third approach: Count number of calls to f3, given by a “recurrence relation” for C(N).

This approach not covered in class. Provided for those of you who want to see a recurrence relation solution.

public static int f3(int n) {

if (n <= 1)

return 1;

return f3(n-1) + f3(n-1)

}

​

Mergesort

Lecture 15, CS61B, Fall 2024

Summations

Analyzing Programs

• Nested For Loops
• Amortized Analysis
• Recursive Analysis

Mergesort

Sorting

Along with matrix multiplication, sorting is one of the problems that pops up most often in asymptotic analysis.

• Given a list of Comparables, return them in sorted order
• Assumes the comparison method has certain properties, and runs in Θ(1) time.

​

x = List.of({“he”, “is”, “the”, “agoyatis”, “of”, “mr.”, “conchis”})

public static List<Comparable> sort(List<Comparable> x)

x = {“agoyatis”, “conchis”, “he”, “is”, “mr.”, “of”, “the”}

Mergesort Pseudocode

Mergesort is a recursive way to sort a list:

• Split the list into two parts
• Sort the two lists individually
• Merge the two lists together

static List<Comparable> sort(List<Comparable> x)

List<Comparable> firsthalf = sort(x.sublist(0, x.size()/2));

List<Comparable> secondhalf = sort(x.sublist(x.size()/2, x.size()));

return merge(firsthalf, secondhalf);

}

​

The Merge Operation

Given two sorted arrays, the merge operation combines them into a single sorted array by successively copying the smallest item from the two arrays into a target array.

​

Merging Demo (Link)

Merge Runtime

How does the runtime of merge grow with N, the total number of items?

1. Θ(1) C. Θ(N)
2. Θ(log N) D. Θ(N²)

2

3

6

10

11

4

5

7

8

2

3

4

5

6

7

8

10

11

Merge Runtime

How does the runtime of merge grow with N, the total number of items?

C. Θ(N). Why? Θ(1) time per element in the merged list, and the merged list has exactly N items

2

3

6

10

11

4

5

7

8

2

3

4

5

6

7

8

10

11

Determining Mergesort Runtime

Since we don't care about the list itself, let's simplify our code a bit

• Our runtime should be in terms of x.size(), so let's let int n = x.size()
• merge takes Θ(n) time, so let's replace that with "n units of work"

static List<Comparable> sort(List<Comparable> x)

List<Comparable> firsthalf = sort(x.sublist(0, x.size()/2));

List<Comparable> secondhalf = sort(x.sublist(x.size()/2, x.size()));

return merge(firsthalf, secondhalf);

}

​

Determining Mergesort Runtime

Since we don't care about the list itself, let's simplify our code a bit

• Our runtime should be in terms of x.size(), so let's let int n = x.size()
• merge takes Θ(n) time, so let's replace that with "n units of work"

static void sortRuntime(int n)

sortRuntime(n/2);

sortRuntime(n/2);

//n units of work

}

​

Example 5: Mergesort Order of Growth

For an array of size N, what is the worst case runtime of Mergesort?

1. Θ(1)
2. Θ(log N)
3. Θ(N)
4. Θ(N log N)
5. Θ(N²)

N/4

N/8

N/8

static void sortRuntime(int n)

sortRuntime(n/2);

sortRuntime(n/2);

//n units of work

}

​

Example 5: Mergesort Order of Growth

Mergesort has worst case runtime = Θ(N log N).

• Every level has N units of work.
• Top level takes N units of work.
• Next level takes N/2 + N/2 = N units of work.
• One more level down: N/4 + N/4 + N/4 + N/4 = N.
• Thus, total runtime is Nk, where k is the number of levels.
• How many levels? Goes until we get to size 1.
• k = log₂(N).
• Overall runtime is Θ(N log N).

​

Exact count explanation is tedious.

• Omitted here.

N/4

N/8

N/8

Mergesort using Recurrence Relations (Extra)

C(N): Number of calls to mergesort + number of array writes.

N/4

N/8

N/8

Using Sorting as a Tool

Recall from Lecture 11 the dup functions, which checked if a sorted array contained any duplicates.

• dup1 took Θ(N²) runtime, while dup2 took Θ(N) runtime

What if the input wasn't sorted?

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;

}

public static boolean dup2(int[] A) {

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

if (A[i] == A[i + 1]) {

return true;

}

}

return false;

}

​

​

dup1

dup2

Using Sorting as a Tool

What if the input wasn't sorted?

• dup1 still works normally, but it takes Θ(N²) runtime
• dup2 no longer works… Can we fix it?

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;

}

public static boolean dup2(int[] A) {

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

if (A[i] == A[i + 1]) {

return true;

}

}

return false;

}

​

​

dup1

dup2

Using Sorting as a Tool

What if the input wasn't sorted?

• Solution: Sort A first!
• What's our new runtime?
• Sorting took Θ(N log N) time, the rest of dup2 took Θ(N) time

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;

}

public static boolean dup2(int[] A) {

A = A.sort()

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

if (A[i] == A[i + 1]) {

return true;

}

}

return false;

}

​

​

dup1

dup2

Using Sorting as a Tool

What if the input wasn't sorted?

• dup1 still works normally, but it takes Θ(N²) runtime
• If we use sort as a black box, we can modify dup2 so it runs in Θ(N log N) time!
• Can we do better? Yes, we can get Θ(N)... once we get to hashing

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;

}

public static boolean dup2(int[] A) {

A = A.sort()

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

if (A[i] == A[i + 1]) {

return true;

}

}

return false;

}

​

​

dup1

dup2

Linear vs. Linearithmic (N log N) vs. Quadratic

N log N is basically as good as N, and is vastly better than N².

• For N = 1,000,000, the log N is only 20.

(from Algorithm Design: Tardos, Kleinberg)

Summary

Theoretical analysis of algorithm performance requires careful thought.

• There are no magic shortcuts for analyzing code.
• In our course, it’s OK to do exact counting or intuitive analysis.
• Know how to sum 1^k+2^k+...+N^k and k⁰+k¹+...+k^N.
• We won’t be writing mathematical proofs in this class.
• Many runtime problems you’ll do in this class resemble one of the five problems from today. See textbook, study guide, and discussion for more practice.
• This topic has one of the highest skill ceilings of all topics in the course, and is a modern research topic

Different solutions to the same problem, e.g. sorting, may have different runtimes.

• N² vs. N log N is an enormous difference.
• Going from N log N to N is nice, but not a radical change.

Once you prove runtime for one problem, you may be able to use it in other problems to speed things up!

​

​

Binary Search (Intuitive)

Lecture 15, CS61B, Fall 2024

Summations

Analyzing Programs

• Nested For Loops
• Amortized Analysis
• Recursive Analysis

Mergesort

Binary Search (If time allows)

• Intuitive Approach
• Exact Approach

​

Binary Search (demo: https://goo.gl/3VvJNw)

Trivial to implement?

• Idea published in 1946.
• First correct implementation in 1962.
• Bug in Java’s binary search discovered in 2006.

See Jon Bentley’s book Programming Pearls.

See http://goo.gl/gQI0FN

static int binarySearch(String[] sorted, String x, int lo, int hi)

if (lo > hi) return -1;

int m = (lo + hi) / 2;

int cmp = x.compareTo(sorted[m]);

if (cmp < 0) return binarySearch(sorted, x, lo, m - 1);

else if (cmp > 0) return binarySearch(sorted, x, m + 1, hi);

else return m;

}

​

Binary Search (Intuitive)

Goal: Find runtime in terms of N = hi - lo + 1 [i.e. # of items being considered]

• Intuitively, what is the order of growth of the worst case runtime?
• 1
• log₂ N
• N
• N log₂ N
• 2^N

static int binarySearch(String[] sorted, String x, int lo, int hi)

if (lo > hi) return -1;

int m = (lo + hi) / 2;

int cmp = x.compareTo(sorted[m]);

if (cmp < 0) return binarySearch(sorted, x, lo, m - 1);

else if (cmp > 0) return binarySearch(sorted, x, m + 1, hi);

else return m;

}

​

Binary Search (Intuitive)

Goal: Find runtime in terms of N = hi - lo + 1 [i.e. # of items being considered]

• Intuitively, what is the order of growth of the worst case runtime?

B. log₂N

​

​

Why? Problem size halves over and over until it gets down to 1.

• If C is number of calls to binarySearch, solve for 1 = N/2^C → C = log₂(N)

static int binarySearch(String[] sorted, String x, int lo, int hi)

if (lo > hi) return -1;

int m = (lo + hi) / 2;

int cmp = x.compareTo(sorted[m]);

if (cmp < 0) return binarySearch(sorted, x, lo, m - 1);

else if (cmp > 0) return binarySearch(sorted, x, m + 1, hi);

else return m;

}

​

N

≈N/2

≈N/4

≈N/8

Log Time Is Really Terribly Fast

In practice, logarithmic time algorithms have almost constant runtimes.

• Even for incredibly huge datasets, practically equivalent to constant time.

Binary Search Exact (Bonus)

Lecture 15, CS61B, Fall 2024

Summations

Analyzing Programs

• Nested For Loops
• Amortized Analysis
• Recursive Analysis

Mergesort

Binary Search (If time allows)

• Intuitive Approach
• Exact Approach

This section is available as a pre-recorded video.

​

It's not ”out of scope” since it’s just another example problem using the same techniques used throughout the lecture.

Binary Search (Exact Count): Not a Live Video (no yellkey)

Goal: Find worst case runtime in terms of N = hi - lo + 1 [i.e. # of items]

Each call does constant work (w/o recursive calls)

• What is C(6), number of total calls for N = 6?
• 6 D. 2
• 3 E. 1
• log₂(6)=2.568

​

static int binarySearch(String[] sorted, String x, int lo, int hi)

if (lo > hi) return -1;

int m = (lo + hi) / 2;

int cmp = x.compareTo(sorted[m]);

if (cmp < 0) return binarySearch(sorted, x, lo, m - 1);

else if (cmp > 0) return binarySearch(sorted, x, m + 1, hi);

else return m;

}

​

N=6

Binary Search (Exact Count)

Goal: Find worst case runtime in terms of N = hi - lo + 1 [i.e. # of items]

Each call does constant work (w/o recursive calls)

• What is C(6), number of total calls for N = 6?

B. 3

​

Three total calls, where N = 6, N = 3, and N = 1.

static int binarySearch(String[] sorted, String x, int lo, int hi)

if (lo > hi) return -1;

int m = (lo + hi) / 2;

int cmp = x.compareTo(sorted[m]);

if (cmp < 0) return binarySearch(sorted, x, lo, m - 1);

else if (cmp > 0) return binarySearch(sorted, x, m + 1, hi);

else return m;

}

​

N=6

N=3

N=1

3 calls

Binary Search (Exact Count)

Goal: Find worst case runtime in terms of N = hi - lo + 1 [i.e. # of items]

• Number of binarySearch calls.

static int binarySearch(String[] sorted, String x, int lo, int hi)

if (lo > hi) return -1;

int m = (lo + hi) / 2;

int cmp = x.compareTo(sorted[m]);

if (cmp < 0) return binarySearch(sorted, x, lo, m - 1);

else if (cmp > 0) return binarySearch(sorted, x, m + 1, hi);

else return m;

}

​

N

C(N)

N=1

Binary Search (Exact Count)

Goal: Find worst case runtime in terms of N = hi - lo + 1 [i.e. # of items]

• Number of binarySearch calls.

static int binarySearch(String[] sorted, String x, int lo, int hi)

if (lo > hi) return -1;

int m = (lo + hi) / 2;

int cmp = x.compareTo(sorted[m]);

if (cmp < 0) return binarySearch(sorted, x, lo, m - 1);

else if (cmp > 0) return binarySearch(sorted, x, m + 1, hi);

else return m;

}

​

N=1

N

C(N)

N=2

N=3

Binary Search (Exact Count)

Goal: Find worst case runtime in terms of N = hi - lo + 1 [i.e. # of items]

• Number of binarySearch calls.

static int binarySearch(String[] sorted, String x, int lo, int hi)

if (lo > hi) return -1;

int m = (lo + hi) / 2;

int cmp = x.compareTo(sorted[m]);

if (cmp < 0) return binarySearch(sorted, x, lo, m - 1);

else if (cmp > 0) return binarySearch(sorted, x, m + 1, hi);

else return m;

}

​

N=1

N

C(N)

N=2

N=3

4

5

6

7

Binary Search (Exact Count)

Goal: Find worst case runtime in terms of N = hi - lo + 1 [i.e. # of items]

• Number of binarySearch calls.

static int binarySearch(String[] sorted, String x, int lo, int hi)

if (lo > hi) return -1;

int m = (lo + hi) / 2;

int cmp = x.compareTo(sorted[m]);

if (cmp < 0) return binarySearch(sorted, x, lo, m - 1);

else if (cmp > 0) return binarySearch(sorted, x, m + 1, hi);

else return m;

}

​

N=1

N

C(N)

N=2

N=3

4

5

6

7

8

9

...

Binary Search (Exact Count)

Goal: Find worst case runtime in terms of N = hi - lo + 1 [i.e. # of items]

• Number of binarySearch calls.

static int binarySearch(String[] sorted, String x, int lo, int hi)

if (lo > hi) return -1;

int m = (lo + hi) / 2;

int cmp = x.compareTo(sorted[m]);

if (cmp < 0) return binarySearch(sorted, x, lo, m - 1);

else if (cmp > 0) return binarySearch(sorted, x, m + 1, hi);

else return m;

}

​

N=1

N

C(N)

N=2

N=3

4

5

6

7

8

9

...

C(N) = ⌊log₂(N)⌋+1

Binary Search (Exact Count)

Goal: Find worst case runtime in terms of N = hi - lo + 1 [i.e. # of items]

• Number of binarySearch calls.
• C(N) = ⌊log₂(N)⌋+1
• Since each call takes constant time, R(N) = Θ(⌊log₂(N)⌋)
• This f(N) is way too complicated. Let’s simplify.

static int binarySearch(String[] sorted, String x, int lo, int hi)

if (lo > hi) return -1;

int m = (lo + hi) / 2;

int cmp = x.compareTo(sorted[m]);

if (cmp < 0) return binarySearch(sorted, x, lo, m - 1);

else if (cmp > 0) return binarySearch(sorted, x, m + 1, hi);

else return m;