Section 2

Runtime

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!

�

Big-Omega and Big-Theta

Practice

Practice

1. Always True
2. Always True
3. Sometimes True
4. Always True
5. Sometimes True
6. Sometimes True
7. Sometimes True
8. Always False

Worksheet problems

1. Prove that f(n) ∈ O(g)

​

1. f(n) = 7n, g(n) = n/10
2. f(n) = 1000, g(n) = 3n³
3. f(n) = 2ⁿ, g(n) = 3²ⁿ
4. f(n) = 7n² + 3n, g(n) = n⁴
5. f(n) = n + 2nlog(n), g(n) = nlog(n)

How to Approach these Problems

When trying to prove something like f(n) ∈ O(g) or f(n) ∈ Ω(g), you need to find a c and n₀.

• The proof, or final solution, for the problem should simply declare the values of c and n₀ and should plug them in/explain why they make the inequality true.
• The proof should not explain how to solve for c and n₀- that would be your own work.

​

1a) Proof - Final Solution

1b) Proof - Final Solution

1c) Proof - Final Solution

1d) Proof - Final Solution

1e) Proof - Final Solution

Worksheet problems

2. We provide functions f(n) and g(n). Prove that f(n) ∈ Θ(g)

​

1. f(n) = 7n, g(n) = n/10�
2. f(n) = n³ + 10n, g(n) = 3n³

How to Approach these Problems

When trying to prove a function f(n) ∈ Θ(g), you should show that f(n) ∈ O(g) and f(n) ∈ Ω(g).

• The proof, or final solution, for the problem consists of both a big-O and big-Omega proof
• Each sub-proof should simply declare values of c and n₀ and plug them in/explain why they make the inequality true.
• The proof should not explain how to solve for c and n₀- that would be your own work.

2a) Proof - Final Solution

2b) Proof - Final Solution Part 1

2b) Proof - Final Solution Part 2

Worksheet problems: Q3

Get the Θ(·) bound of each function below.

1. f(n) = worst case running time
2. g(n) = best case running time

​

We will construct equations for each function and then simplify them to get a closed form.

3a) f(n) = worst case running time

First function (lines 3-5) always runs once.

​

Worst case for lines 7-16 is if every value in array is unique. This means for every iteration of the outer loop, the inner loop will iterate through the rest of the array. Total number of iterations is n + (n-1) + (n-2) + … + 1.

There is a formula for this sum: n * (n+1) / 2

​

f(n) = n + n(n+1)/2 => n². This is quadratic running time

​

Do something similar to Q2 proofs to prove that n + n(n+1)/2 ∈ Θ(n²).

​

​

3b) g(n) = best case running time

First function (lines 3-5) always runs once.

​

Best case for lines 7-16 is if every value in array is the same. This means the inner loop will only run once: for the first iteration of the outer loop. Then, it will not run because every index will be visited after the first time.

​

g(n) = n + n => n

This is linear running time

​

Do something similar to Q2 proofs to prove that n + n ∈ Θ(n).

​