1 of 35

Section 2

Runtime

2 of 35

Big-O 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 35

Big-Omega and Big-Theta

4 of 35

Practice - Page 1 ( 0. True/False Questions)

 

5 of 35

Practice - Page 1 ( 0. True/False Questions)

 

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

6 of 35

Big-Oh Proofs!

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

​

  1. f(n) = 7n, g(n) = n/10
  2. f(n) = 1000, g(n) = 3n3
  3. f(n) = 2n, g(n) = 32n
  4. f(n) = 7n2 + 3n, g(n) = n4
  5. f(n) = n + 2nlog(n), g(n) = nlog(n)

7 of 35

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

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

​

8 of 35

 

 

 

scratchwork…

9 of 35

1a) Proof - Final Solution

10 of 35

 

 

scratchwork…

11 of 35

1b) Proof - Final Solution

12 of 35

scratchwork…

13 of 35

1c) Proof - Final Solution

14 of 35

 

 

scratchwork…

15 of 35

1d) Proof - Final Solution

16 of 35

 

 

scratchwork…

17 of 35

1e) Proof - Final Solution

18 of 35

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) = n3 + 10n, g(n) = 3n3

19 of 35

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 n0 and plug them in/explain why they make the inequality true.
  • The proof should not explain how to solve for c and n0- that would be your own work.

20 of 35

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 n0 and plug them in/explain why they make the inequality true.
  • The proof should not explain how to solve for c and n0- that would be your own work.

big-O proof! big-Omega proof!

​

Together, we make a big-Theta proof!

21 of 35

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

22 of 35

 

 

scratchwork…

23 of 35

2a) Proof - Final Solution

24 of 35

scratchwork…

25 of 35

2b) Proof - Final Solution Part 1

 

26 of 35

2b) Proof - Final Solution Part 2

27 of 35

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.

28 of 35

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

length of values

setting visited[i]

(why not also incrementing out?)

alright this is really long so let’s go this step by step/line by line

29 of 35

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

Let’s approach this step by step.

​

Looking at our first loop…

What is its runtime?

30 of 35

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

Let’s approach this step by step.

​

Looking at our first loop…

What is its runtime?

n

​

time per iteration: 1

loop iterations: values.length, so n

whole loop takes: 1 * n = n time

​

31 of 35

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

} n

Okay now looking at our second loop…

What is its runtime?

(Important: Think of worst case input!)

32 of 35

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

} n

Okay now looking at our second loop…

What is its runtime?

(Important: Think of worst case input!)

n * (n+1) / 2

​

worst case is if every element in values is unique. this would mean for every iteration of the outer loop, the inner loop iterates through the entire rest of the array.

​

so, total # of iterations is:

n + (n-1) + (n-2) + … + 1

= n * (n+1) / 2

​

33 of 35

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

First loop (lines 3-5) always runs once. it has n runtime.

​

Worst case for second loop (lines 7-16) is if every value in array is unique. it has n(n+1)/2 runtime.

​

so for our whole method numUnique, our worst case runtime:

​

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

​

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

​

​

} n

n(n+1)/2

}

34 of 35

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

In 3a), we went over worst case.

​

Now try: best case!

35 of 35

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

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

​

Best case for second loop (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

​

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

​