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

Practice

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), f(n) ∈ Ω(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

Let c = 70 and n₀= 1. Show ∀n >= 1, 7n <= 70 * n/10

7n <= 70 * n/10

≡ 7n <= 7n

≡ n <= n

​

This is true because n = n ∀n >= 1 (and also for ∀n in general), meaning that n <= n too.

​

1b) Proof - Final Solution

Let c = 1 and n₀= 20. Show ∀n >= 20, 1000 <= 1 * 3n²

1000 <= 1 * 3n²

≡ 1000/3 <= n²

​

This is true because n² is strictly increasing and 20² > 1000/3

1c) Proof - Final Solution

Let c = 1 and n₀= 2. Show ∀n >= 2, 2ⁿ <= 1 * 3²ⁿ

​

2ⁿ <= 1 * 3²ⁿ

≡ 2ⁿ <= 9ⁿ

≡ 1 <= (9/2)ⁿ

≡ 1 <= 4.5ⁿ

This is true because 4.5ⁿ is strictly increasing and 4.5² >= 1

1d) Proof - Final Solution

Let c = 10 and n₀= 1. Show ∀n >= 1, 7n² + 3n <= 10n⁴

​

7n² + 3n <= 10n⁴

(no more simplifying necessary unless you want to)

​

This is true because both sides are strictly increasing and an exponent of 4 is larger than exponent of 2. Also, 10(1)⁴ = 7(1)² + 3(1)

1e) Proof - Final Solution

Let c = 3 and n₀= 2. Show ∀n >= 2, n + 2nlog(n) <= 3nlog(n)

​

n + 2nlog(n) <= 3nlog(n)

≡ n <= nlog(n)

≡ 1 <= log(n) we can do this because n >= 2

​

This is true because log(n) is strictly increasing and log(2) = 1

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³

2a) Proof - Final Solution

We proved the first part in Q1. Now, let c = 70 and n₀= 1 and show ∀n >= 1, 7n >= 70 * n/10

​

7n >= 70 * n/10

≡ 7n >= 7n

≡ n >= n

​

This is true because n = n ∀n >= 1 (and also for ∀n in general), meaning that n >= n too. Therefore, we proved that f(n) ∈ Θ(g).

2b) Proof - Final Solution Part 1

First let c = 1 and n₀= 3 and show ∀n >= 3, n³ + 10n <= 1 * 3n³

n³ + 10n <= 1 * 3n³

≡ 10n <= 2n³

≡ 5n <= n³

≡ 5 <= n² we can do this because n >= 3

​

This is true because n² is strictly increasing and 3² >= 5

2b) Proof - Final Solution Part 2

First let c = ⅓ and n₀= 1 and show ∀n >= 1, n³ + 10n >= ⅓ * 3n³

n³ + 10n >= ⅓ * 3n³

≡ n³ + 10n >= n³

≡ 10n >= 0

≡ n >= 0

​

This is true because we claimed that n >= 1, and 1 > 0. Therefore, we proved that f(n) ∈ Θ(g).

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).

​