**You are being recorded and transcribed.**

*Approximate overview*

- Administrivia
- Questions
- Review of our loop problem from last class
- A more formal definition of Big-O
- Analyzing recursive procedures

- Looking ahead: You will be getting your sleep disrupted this weekend.
- The new tokens assignment is posted. I’m working on copying things over from the old tokens assignment.
- Sorry that grading is so slow. I’m trying!
- MP6 will be coming out tomorrow. Sorry for the delay.

- Wednesday, 2024-03-06, 11pm, MP5
- Friday, 2024-03-08, 1pm, Readings
- Friday, 2024-03-08, 11pm, MP5 post-reflection
- Friday, 2024-03-08, 11pm, MP6 pre-reflection
- Sunday, 2024-03-10, 11pm, MP1 redo
*Submit MP1 redo on Gradescope*- Please don’t submit until it’s ready for grading.

- Sunday, 2024-03-10, 11pm, MP2 redo
*Submit MP2 redo on Gradescope*- Please ask if you’re confused about something.

- Friday, 2024-03-15, 11pm, Third set of LAs.

Academic/Scholarly

- Thursday, 2024-03-07, 11:00 a.m.,JRC 101.
*Scholars’ Convocation: An American Genocide: The United States and the California Indian Catastrophe, 1846-1873* - Thursday, 2024-03-07, 4:00 p.m., Science 3821.
*CS Extras*. - Tuesday, 2024-03-12, noon, Some PDR.
*CS Table*. - Tuesday, 2024-02-12, 8:00–9:00pm, Science 3821.
*CSC-207 Mentor Session*.

Cultural

- Thursday, 2024-03-07, JRC 101, 8:00-9:30 pm.
*Writers@Grinnell: Carl Phillips* - Friday at 4pm in the Global Living Room.
*Middle of Everywhere*. - Saturday, 2024-03-09, Harris Cinema, ??:??
*Met Opera: Verdi’s La Forza del Destino*. - Saturday, 2024-03-09, 2:00 pm, Sebring-Lewis.
*ZAWA!*(Flute concert).

Peer

- Thursday–Saturday, 2024-03-07 to 2024-03-09, 7:30 p.m.
*Songs of the Scarlet and Wayback*(play).- Tickets go “on sale” tomorrow at noon.
- Thursday is a “pre-view” performance.

- Friday, 2024-03-08, 4:00–6:00 p.m. Art Museum
*Women’s Day Presentations*. - Saturday, 2024-03-09, Field House.
*Men’s and Women’s Tennis vs. Central.*

Wellness

- Wednesday, 2024-03-06, 4pm, JRC 101.
*Intimacy Stages*. - Friday, 2024-03-08, noon, JRC 101.
*Wellness Bingo*. - Tuesday, 2024-03-12, noon-1pm, BRAC P103.
*HIIT and Strength Fitness Class.* - Tuesday, 2024-03-12, 12:15–12:50, Bucksbaum 131.
*Yoga in the Museum.* - Tuesday, 2024-03-12, 4pm, BRAC P103 (Multipurpose Dance Studio):
*Yoga*.

Misc

How do you know Sam has read the requests for tokens?

He hasn’t.

When will we know?

Some day. By the end of break. I cancelled MP6 to give you some (slack) teams. Give me some, too.

Do I have to modify `AAC.java`

?

No. But you may want to read it.

What’s the hidden assumption in `getCategory`

?

You’ll return the empty string for the top-level category.

AAC.java doesn’t seem to handle exceptions. What should we do?

Ignore them?

Let it crash (or print the exception to a terminal).

Where should I add the `try/catch`

clause to handle the exceptions
in `AssociativeArray`

?

Probably in

`AACCategory.java`

and`AACMappings.java`

.

The specs are inconsistent. What should I do?

Whatever you think is better.

```
int count;
for (int i = 1; i <= n; i *= 2) {
for (int j = 0; j < i; j++) {
count++;
} // for
} // for
```

Is this O(2.5^n) O(n^2), O(nlogn), O(n), O(logn), O(1) or …?

It’s definitely O(n^100) or O(n!) or O(2^n). We want a tighter bound.

One analysis:

- The outer loop runs O(logn) times.
- At worst, the inner loop runs O(n) times.
- If each time we run the outer loop, we have the worst case of the inner loop, that will be O(nlogn).

Some experimental notes:

- When n is 1: 1
- When n is 2: 3 = 1 + 2
- WHen n is 3: 3
- When n is 4: 7 = 1 + 2 + 4
- When n is 5: 7
- WHen n is 6: 7
- When n is 7: 7
- When n is 8: 15 = 1 + 2 + 4 + 8
- When n is 16: 31 = 1 + 2 + 4 + 8 + 16
- When n is 32: 63 = 1 + 2 + 4 + 8 + 16 + 32

What’s the pattern? When n is a power of 2 (2^k), it’s the next power of two minus 1. (2^(k+1) - 1). 2n-1. Which is in O(n)

- When n is 2048: 4095

A function, f(n) is in O(g(n)) iff exists c > 0, n_0 > 0, such that, for all n greater than n_0, f(n) <= c*g(n).

Example, we know that f(n) = n is in O(g(n)) where g(n) = 2n-1.

Let c = 1, let n_0 = 5. Is n < 2n-1 for n > 5?

- n <= 2n-1
- iff 0 <= n - 1
- iff 1 <= n

Parsing the original

`<=`

: “is bounded above above”`c*g(n)`

: a constant times g(n); “something with the same shape as g(n)”`n > n_0`

: “for sufficiently large input

Another way to think of Big-O.

f(n) is in O(g(n)) iff exists a constant, d, s.t., lim as n approaches infinity of |f(n)/g(n)| <= d.

- Informal usage: Lets us bound algorithms.
- Formal definition: Lets us prove things about how we can use the notation.
- If f(n) is in O(q*g(n)), where q is a constant, f(n) is also in O(g(n)).
- We can ignore leading constants. O(2n) = O(n) = O(1/2 * n) = O(1000n).

- If f(n) is in O(g(n) + h(n)) and g(n) is in O(h(n)), then
f(n) is in O(h(n))
- We can throw away lower-order terms. E.g., if f(n) is in O(n^2 + 2n), then f(n) is also in O(n^2).

- If f(n) is in O(g(n)) and g(n) is in O(h(n)), then f(n) is in O(h(n)).
- Transitive property.

- If f(n) is in O(q*g(n)), where q is a constant, f(n) is also in O(g(n)).

We will write a lot of recursive algorithms. Some recursive algorithms are difficult to make iterative. So we should analyze them directly.

We start by developing a recurrence relation. I.e., a set of equations or inequalities that tell us about the running time of our function.

- T(1) = 1.
- T(n) = 2T(n/2) + n

Is T(n) in O(n)? O(n^2)? O(logn)? …

Goal: Turn T(n) into a non-recursive formula.

(At least) four approaches:

- Substitution
- Top-down
- Bottom-up

- Draw a recursion tree
- The poorly named “master method”. Express according to a particular form and then plug into a formula.

*Side note: This is why faculty give quizzes and reading reflections.*

Back to our example up approach.

- T(1) = 1.
- T(n) = 2T(n/2) + n

Bottom-up (much like what we did for the loop)>

- T(1) = 1
- T(2) = 2
*T(1) + 2 = 2*1 + 2 = 4 = (2*2) - T(4) = 2
*T(2) + 4 = 2*4 + 4 = 12 = (3*4) - T(8) = 2
*T(4) + 8 = 2*12 + 8 = 32 = (4*8) - T(16) = 2
*T(8) + 16 = 2*32 + 16 = 80 = (5*16) - T(2^k) = (k+1)*(2^k)

Let n = 2^k. That means that k = log_2(n)

- T(n) = (log2n+1)*n = O(nlog2n + n) = O(nlog2n) = O(nlogn)

Top-down approach (substitution)

- T(m) = 2T(m/2) + m

Analysis

*T(n) = 2T(n/2) + n.*- T(n/2) = 2T(n/4) + n/2

- T(n) = 2*(2T(n/4) + n/2) + n
- T(n) = 4*T(n/4) + n + n
*T(n) = 4*T(n/4) + 2n*- T(n/4) = 2T(n/8) + n/4

- T(n) = 4*(2T(n/8) + n/4) + 2n
- T(n) = 8T(n/8) + n + 2n
*T(n) = 8T(n/8) + 3n*- T(n/8) = 2*T(n/16) + n/8

- T(n) = 8
*(2*T(n/16) + n/8) + 3n - T(n) = 16*T(n/16) + n + 3n
*T(n) = 16*T(n/16) + 4n*

We see a pattern. Maybe. Something involving 2^k.

- T(n) = (2^k)*T(n/2^k) + kn.

Let n = 2^k.

- T(n) = n * T(n/n) + log_2(n)*n
- T(n) = n * T(1) + log_2(n)*n
- T(n) = n * 1 + log_2(n)*n
- T(n) = n + log_2(n)*n
- T(n) is in O(nlogn).

Third option: Pictures! (See whiteboard)

- Each level of the tree requires O(n) work.
- There are O(logn) levels.
- There is therefore O(nlogn) total work.

Which of these is best?

- Each of us responds differently.

- T(n) = 2T(n/2) + 1
- T(1) = 1

Solution

- T(n) is in O(n)

Bottom-up approach

- T(1) = 1
- T(2) = 3
- T(4) = 7
- T(8) = 15
- T(16) = 31

Second problem

- T(n) = T(n/2) + n
- T(1) = 1

Third problem

- T(n) = T(n/2) + 1
- T(1) = 1