Announcements

Upcoming Deadlines:

• Project 2 basics autograder due 3/2 at 11:59 PM.
• Project 2 due 3/7 at 11:59 PM. Autograder will be minimal since it largely will involve manual testing.
• No lab this week: It will be project 2 office hours instead.

​

Lecture today/friday somewhat more slowly paced (given project).

• Today: Practice with what we learned Monday.

​

See study guides for each lecture starting Monday:

• Webcast viewers, do all B-level problems in guide before watching this lecture.

​

CS61B

Lecture 18: Asymptotics II: Analysis of Algorithms

• Review of Asymptotic Notation
• Examples 1-2: For Loops
• Example 3: A Basic Recurrence
• Example 4: Binary Search
• Example 5: Mergesort

Summary of Asymptotic Notations

From discussion

Example 1/2:For Loops

Monday’s Lecture

We discussed ways to analyze algorithm performance. To understand how code scales, we symbolically count number of executions of a representative operation as a function of input size N.

• Focus on behavior for large N: ignore lower order terms.
• Ignore constant multiplicative factors.

int count = 0, N = a.length;

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

if (a[i] == k) {

count += 1;

}

}

a[k] += count;

Big Theta formalizes our intuitive simplifications.

Example 1: Nested For Loops

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

0

1

2

3

4

5

i

j

0 1 2 3 4 5

Example 1: Nested For Loops

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

Worst case number of j += 1 calls:

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

(N-1)/2 of these combinations

Overall worst case runtime: Θ(N²)

0

1

2

3

4

5

0 1 2 3 4 5

i

j

1 + (N-1) = N

N

N

= N(N-1)/2

Example 1: Nested For Loops

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

Worst case number of j += 1 calls:

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

Overall worst case runtime: Θ(N²)

0

1

2

3

4

5

0 1 2 3 4 5

i

j

= N(N-1)/2

Overall worst case runtime: Θ(N²)

Nested For Loops II: PollEv.com/jhug or JHUG to 37607

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. Something else

Nested For Loops II: PollEv.com/jhug or JHUG to 37607

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

Cost model, println(“hello”) calls:

0

1

2

3

4

5

0 1 2 3 4 5

j

i

n=1

Nested For Loops II: PollEv.com/jhug or JHUG to 37607

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

Cost model, println(“hello”) calls:

0

1

2

3

4

5

0 1 2 3 4 5

j

i

n=1

Nested For Loops II: PollEv.com/jhug or JHUG to 37607

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

Cost model, println(“hello”) calls:

0

1

2

3

4

5

0 1 2 3 4 5

j

i

n=1

n=2

,3

Nested For Loops II: PollEv.com/jhug or JHUG to 37607

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

Cost model, println(“hello”) calls:

0

1

2

3

4

5

0 1 2 3 4 5

j

i

n=1

n=2

,3

n=4

,5,6,7

Nested For Loops II: PollEv.com/jhug or JHUG to 37607

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

Cost model, println(“hello”) calls:

0

1

2

3

4

5

0 1 2 3 4 5

j

i

n=1

n=2

,3

n=4

,5,6,7

n=8,9,10, …, 15

Nested For Loops II: PollEv.com/jhug or JHUG to 37607

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

Cost model, println(“hello”) calls:

“Worst case” here is irrelevant, all cases the same.

Cost model, println(“hello”) calls:

• R(N) = Θ(1 + 2 + 4 + 8 + … + N)

D. N log N

E. N²

F. Something else

1. 1
2. log N
3. N

n=1

n=2

,3

n=4

,5,6,7

n=8,9,10, …, 15

Nested For Loops II: PollEv.com/jhug or JHUG to 37607

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

“Worst case” here is irrelevant, all cases the same.

Cost model, println(“hello”) calls:

• R(N) = Θ(1 + 2 + 4 + 8 + … + N)

D. N log N

E. N²

F. Something else

• 1
• log N
• N

Nested For Loops II: PollEv.com/jhug or JHUG to 37607

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

Nested For Loops II: PollEv.com/jhug or JHUG to 37607

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

R(N) = Θ(1 + 2 + 4 + 8 + … + N)

= Θ(N)

• 1
• log N
• N

D. N log N

E. N²

F. Something else

Repeat After Me...

There is no magic shortcut for these problems (well… usually)

• Runtime 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 + 2 + 4 + 8 + … + N = 2N - 1 = Θ(N)

Repeat After Me...

There is no magic shortcut for these problems (well… usually)

• Runtime 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 + 2 + 4 + 8 + … + N = 2N - 1 = Θ(N)
• Strategies:
• Write out examples
• Draw pictures

QR decomposition runtime, from a numerical linear algebra textbook

Example 3: Recursion

Recursion (Intuitive): PollEv.com/jhug or JHUG to 37607

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

Recursion (Intuitive): PollEv.com/jhug or JHUG to 37607

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

Recursion and Recurrence Relations

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

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

• C(1) = 1

​

Recursion and Recurrence Relations

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

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

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

2C(N-1) + 1

Recursion and Recurrence Relations

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

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

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

​

C(N) = 1 + 2 + 4 + 8 + … + ???

Recursion and Recurrence Relations: PollEv.com/jhug or JHUG to 37607

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

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

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

​

C(N) = 1 + 2 + 4 + 8 + … + 2 = ???

1. 2^N C. 2^N+1
2. 2^N-1 D. 2^N+1 + 1

N-1

Sums of Powers of 2 (Revisited)

C(N) = 1 + 2 + 4 + 8 + … + 2 = ???

​

This is just the same sum we saw before, where Q = 2 :

• 1 + 2 + 4 + 8 + … + Q = 2Q - 1 = Θ(Q)

​

C(N) = 1 + 2 + 4 + 8 + … + 2 = 2(2 ) - 1 = 2 - 1

N-1

N-1

N-1

N

N-1

Recursion and Recurrence Relations

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

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

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

​

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

N-1

N

Recursion and Recurrence Relations (Extra)

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

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

This approach not covered in class. Provided for those of you who really want the algebra.

Example 4: Binary Search

Binary Search (demo: http://goo.gl/iSbyRV)

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

Binary Search (Intuitive): PollEv.com/jhug or JHUG to 37607

Let N = hi - lo + 1.

• What is the order of growth of the runtime of binarySearch?
• 1
• log N
• N
• N log N
• 2^N

N=15

N=7

N=3

N=1

for simplicity: assume N=2^k-1 for some k

Binary Search

Approach: Measure number of string comparisons for N = hi - lo + 1.

• C(0) = 0
• C(1) = 1
• C(N) = 1 + C((N-1)/2)

N=15

N=7

N=3

N=1

for simplicity: assume N=2^k-1 for some k

Binary Search

Approach: Measure number of string comparisons for N = hi - lo + 1.

• C(0) = 0
• C(1) = 1
• C(N) = 1 + C((N-1)/2)

Give C(N) in terms of k:

C(N) = ???

N=15

N=7

N=3

N=1

for simplicity: assume N=2^k-1 for some k

Binary Search

Approach: Measure number of string comparisons for N = hi - lo + 1.

• C(0) = 0
• C(1) = 1
• C(N) = 1 + C((N-1)/2)

​

C(N) = 1 + 1 + … + 1 + 0 = k

N=15

N=7

N=3

N=1

for simplicity: assume N=2^k-1 for some k

k

Binary Search

Approach: Measure number of string comparisons for N = hi - lo + 1.

• C(0) = 0
• C(1) = 1
• C(N) = 1 + C((N-1)/2)

​

C(N) = 1 + 1 + … + 1 + 0 = k

N=15

N=7

N=3

N=1

for simplicity: assume N=2^k-1 for some k

k

k = ⌈lg N⌉ = Θ(log N)

lg is short for base 2

Unproven BigTheta Properties We’ve Just Used

Some easy-to-prove properties:

Base of logarithm doesn’t matter. We’ll usually omit it completely!

Log Time Is Really Terribly Fast

Throughout this course we will see ways of doings things in constant vs log time. In practice, the difference is minimal.

A Note on Solving Recurrence Relations

The entire goal is to find a pattern that yields a closed form solution for C(N).

• Use whatever tricks you’d like.
• This is not CS70.
• We’ll not deviate too terribly far from the patterns you’ll see today and in discussion 8 (summing very simple arithmetic and geometric series).
• We will not write rigorous proofs.

Example 5: Merge Sort

Selection Sort: A Prelude to Example 5.

Earlier in class we discussed a sort called selection sort:

• Find the smallest unfixed item, move it to the front, and ‘fix’ it.
• Sort the remaining unfixed items using selection sort.

​

This algorithm requires Θ(N²) comparisons.

• Look at all N unfixed items to find smallest.
• Then look at N-1 remaining unfixed.
• …
• Look at last two unfixed items.
• Done, sum is 2+3+4+5+...+N = Θ(N²)

​

Array Merging of N Total Items (A.length + B.length = N)

What is the runtime for merge? Θ(1), Θ(N), Θ(N²)???

• Θ(N) compares and array accesses.

A

B

The Merge Operation

One way to sort N items:

• Give half of the items away for sorting to one algorithm.
• Give the other half to some other algorithm.
• Merge the results: Θ(N) compares.

Suppose the other two algs are selection sort.

• N=64:
• Merge: ~64 compares.
• Selection sort: ~512 each.

• Still Θ(N²), but faster since N+2*(N/2)² < N²
• ~1088 vs. ~2048 compares for N=64.

Example 5: Merge Sort

One way to sort N items:

• Give half of the items away for sorting to one algorithm.
• Give the other half to some other algorithm.
• Merge the results: Θ(N) compares.

​

Suppose they each use merge sort.

• N=64:

​

64

32

32

16

16

16

….

8

8

….

64

32

32

16

16

16

8

8

• Top level: 64 compares
• Next level: 64=32 + 32 compares.
• Overall: 64*k compares.
• k = ~lg(64), so ~384 compares.

Merge Sort: More General

Intuitive explanation:

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

N/4

N/8

N/8

Merge Sort: Same Idea as Previous Slide, but Using Algebra

C(N): Number of items merged at each stage.

N/4

N/8

N/8

Linear vs. Linearithmic (N log N)

N log N is basically as good as N.

• Only a tiny bit slower. N = 1,000,000, and the log N is only 20.

Summary

Theoretical analysis of algorithm performance requires careful thought.

• Finding a simple expression for runtime is about finding patterns.
• Know the patterns we’ve learned today (more in HW and discussion).

​

Different solutions to the same problem may have radically different runtimes. N² vs. N log N kind of a big deal.

​

Next time:

• Amortized analysis.
• Empirical measurement of program runtime.
• Sneak preview of complexity theory (extra).