Remember, "the answer" is only half of it! Also, make sure everyone in your group can explain why.

We will use this Gradescope Online Assignment as our worksheet for in-class work. These problems are coded as being worth points for our simplicity, but will not impact your grade in the course.

Question 2

Question 2.1

Recall that Big-Oh is an upper bound, meaning that any function that $f(n) = n^2$ is greater than as $n$ approaches infinity is bound by $\mathcal{O}(n^2)$.

Question 2.2

Recall that Big-Omega is an lower bound, meaning that any function that grows at least as fast as $f(n) = n^2$ as $n$ approaches infinity is bound by $\mathcal{Ω}(n^2)$.

Question 2.3

Recall that Big-Theta represents that "perfect fit" for a function. In other words, to be bound by $\mathcal{Θ}(n^2)$, a function must be both bound by $\mathcal{O}(n^2)$ and $\mathcal{Ω}(n^2)$ as $n$ approaches infinity.

Question 3

Question 3.1

This is fairly similar to the isPrime example from lecture, but it's a little easier to state which inputs of n will cause the slower runtime. The answer is $\mathcal{O}(n)$ since under certain circumstances (for loop when n % 11 == 0) the function will have at most linear runtime as n increases.

Question 3.2

$\Omega(1)$ since no matter what, as n increases, the function will always have at least a constant runtime.

Question 3.3

This function has no theta, since its Big-Oh and Big-Omega bounds are different.

Question 4

Question 4.1

Adding an item to ArrayQueueV2 is often pretty fast ($\Theta(1)$) when there is space in the queue for more items because of the front and back pointers. So the best case is actually most cases when we don't have to resize. However, whenever the queue is full, the array has to resize, which will have a runtime of $\Theta(n)$ since it has to copy data from the smaller to the new larger array.