1 of 23

Section 2

Running Time and Recurrences

2 of 23

Big-Oh Review

Main ideas:

In Big-O, we focus on the growth of the runtime as the input size n goes to infinity.
Big-O represents an upper bound on the algorithm runtime. Not necessarily tight!

�

3 of 23

Big-Omega and Big-Theta

4 of 23

Practice

5 of 23

Practice

6 of 23

Worksheet problems

7 of 23

8 of 23

9 of 23

10 of 23

11 of 23

Worksheet problems

12 of 23

13 of 23

14 of 23

Tree Method Example

…

Red box represents a problem instance

Blue value represents time spent at that level of recursion

15 of 23

Tree Method Idea

…

c

Red box represents a problem instance

Blue value represents time spent at that level of recursion

…

Asymptotically, these never matter!

16 of 23

Base Case Doesn’t Matter!

…

Red box represents a problem instance

Blue value represents time spent at that level of recursion

…

17 of 23

Non-Recursive Constants Don’t Matter!

…

Red box represents a problem instance

Blue value represents time spent at that level of recursion

…

18 of 23

Recursive Constants Do Matter!

…

Red box represents a problem instance

Blue value represents time spent at that level of recursion

19 of 23

Solving the Summation

20 of 23

Recursive Constants Do Matter!

…

Red box represents a problem instance

Blue value represents time spent at that level of recursion

…

21 of 23

Solving the Summation

22 of 23

Recursive Running Times - Guidance

1 of 23

2 of 23

3 of 23

4 of 23

5 of 23

6 of 23

7 of 23

8 of 23

9 of 23

10 of 23

11 of 23

12 of 23

13 of 23

14 of 23

15 of 23

16 of 23

17 of 23

18 of 23

19 of 23

20 of 23

21 of 23

22 of 23

23 of 23