CSCI H343 Data Structures Fall 2023

Time Complexity

We are interested in the running time as the inputs grow large.

We care about the growth rate of an algorithm’s run-time more than it’s value at a particular point.

We focus on the worst-case run-time of algorithms because we want to offer guarantees to the user of an algorithm that hold for all possible inputs.

Our goal is to classify functions that grow at a similar rate, ignoring details that don’t matter.

Functions to think about: n, 10n, lg n, n lg n, 10 n², n² + n

https://www.desmos.com/calculator

Asymptotic Upper Bound

Definition (Big-O) For a given function g, we define O(g) as the the set of functions that grow similarly or slower than g. More precisely, f ∈ O(g) iff ∃ k c. ∀ n ≥ k. f(n) ≤ c g(n).

We say that g(n) is an asymptotic upper bound of all the functions in the set O(g).

Notation We write f ≲ g iff f ∈ O(g), and say that f is asymptotically less-or-equal to g.

Alternatively, the asympotic growth of functions can be characterized using limits.

f ∈ O(g) iff lim{n→∞} f(n)/g(n) is greater or equal zero and not infinity.

Demonstrate the main idea and the role of k and c.

e.g. 4x versus x²

  1. Is 4x ≲ x²?
  2. Is x² ≲ 4x?

e.g. x + 10 versus x

  1. Is x + 10 ≲ x?
  2. Is x ≲ x + 10?

Example Let’s show that (n² + n + 10) ∈ O(n²). So we need to find a constant c such that

n² + n + 10 ≤ c n² when n is large.

We divide both sides by n².

1 + 1/n + 10/n² ≤ c

When n is large, the terms 1/n and 10/n² get very small, so we need to choose something a bit bigger than 1, so we choose c = 2.

Next we need to find a constant k such that

n² + n + 10 ≤ 2 n² when n is greater than k.

We compute a handful of values of these functions.

n n² + n + 10 2n²
1 12 2
2 16 8
3 22 18
4 30 32
5 40 50
6 52 72

We see that from n=4 and onwards, 2n² is greater than n² + n + 10, so we choose k = 4. We have some emprical evidence that we’ve made the correct choices, but to know for sure, we prove the following theorem.

Theorem ∀ n ≥ 4, n² + n + 10 ≤ 2 n².

Proof. We proceed by induction on n.

Student exercise

Show that 2 log n ∈ O(n / 2).

Hint: experiment with values of n that are powers of 2 because it is easy to take the log of them:

log(2) = 1
log(4) = 2
log(8) = 3
...

Reasoning about asymptotic upper bounds