Week 3: Big O Practice

Background

We got introduced to Big-O notation for functions in module 4. Today we're going to practice it with a mix of abstract examples and with concrete examples of algorithms. Finally, time permitting, we will look at the queue ADT and think about the time complexity of different implementations.

Exercise 1

Devise an algorithm whose best polynomial bound for time complexity is O(N³). This algorithm doesn't have to do anything useful, but you should at least come up with pseudocode. If you're interested after you complete the other exercises, you can implement and test this algorithm using the testing framework from module 4 to see if you get a plot that looks like a cubic.

---

Exercise 2

Consider the function \[ f(N) = N^2 \log_2 N + N^3 \] Prove that the function is O(N³). That is, find a constant c and a number n₀ so that \[ f(N) \leq c N^3, N \geq n_0 \]

---

Exercise 3

Let's say we have a timing function \[ T(N) = a \log_2(N^2) \]

Prove that T(N) is O(log(N)). As a hint, recall that \[ \log_a(x^b) = b \log_a(x) \]

---

Exercise 4

We stated that there are algorithms for sorting with timing functions \[ T(N) = aN\log_2(N) \] for some constant a^*. Assuming that python's built-in sorted method for lists takes this amount of time, devise an algorithm where it is impossible to come up with a better time complexity bound than O(N^2 log(N))

Footnote*

Note that the base 2 isn't necessary, because we could apply a change of base formula \[ \log_2(x) = \log_b(x) / \log_b(2) \] and fold in the coefficient (1/log_b(2)) into the constant a, but it's clearer to understand what the algorithm is doing if we leave the base 2 in there, as we will see later

---

Exercise 5

This will most likely be a module exercise, but if groups get to it, let's consider an ADT of a queue. There are two operations in this ADT: enqueue(x) and dequeue(). We can think about this like a line that people stand in to get service. enqueue(x) puts the item x at the back of the line. dequeue() takes out and returns the person at the front of the line. Come up with a data structure that realizes this ADT, and derive tight upper bounds for the time complexity of enqueue and dequeue in your implementation.