Θ Abstracts Away Coefficients
Remember that we also decided that \( \mathrm{C}_{\mathrm{best-inc}}(n) = n\) and \( \mathrm{C}_{\mathrm{worst-inc}}(n) = 2n \)? How about these? Are they \( \Theta(n) \)?
Let's start with \[ \mathrm{C}_{\mathrm{best-inc}}(n): \lim_{n \to \infty} \frac{n}{n} = \lim_{n \to \infty} 1 = 1 \]
So, yes \( \mathrm{C}_{\mathrm{best-inc}}(n) \in \Theta(n) \).
Now let's do \[ \mathrm{C}_{\mathrm{worst-inc}}(n): \lim_{n \to \infty} \frac{2n}{n} = \lim_{n \to \infty} 2 = 2 \]
So, yes \( \mathrm{C}_{\mathrm{worst-inc}}(n) \in \Theta(n) \).
Meh. I feel like I didn't need to take a limit to figure that out.
Sure! Once of the nice things about asymptotic analysis is that it is often possible to eyeball the order of complexity.
The limit definition is there if you are unsure or if you want to double check.
-
We'll start to leave out the limit calculation for examples that we think are clear as we go forward.
Okay, so since both the worst case number of increments and the best case number of increments are \( \Theta(n) \), then, asymptotically, we aren't so concerned about the difference.
So let \( \mathrm{C}_{\mathrm{inc}}(n) \) be the number of increments for an array of size \( n \), for an arbitrary input, one that might not be the best or worst case.
We can't actually write \( \mathrm{C}_{\mathrm{inc}}(n) \) down as a simple expression, we can only say that:
\[ \begin{align} && \mathrm{C}_{\mathrm{best-inc}}(n) & \leq \mathrm{C}_{\mathrm{inc}}(n) \leq \mathrm{C}_{\mathrm{worst-inc}}(n) \\ \Rightarrow && n & \leq \mathrm{C}_{\mathrm{inc}}(n) \leq 2n \end{align} \]
Remember that \( n \) isn't enough information to determine the actual number of increments.
But, we can safely say that \( \mathrm{C}_{\mathrm{inc}}(n) \in \Theta(n) \), because we know that the number of increments is linear in \( n \) no matter what.
Huh. So sometimes \( \Theta \) lets us ignore small complexity differences in different cases of our program.
-
Exactly! That way we can focus on the big picture (in this case: "it's linear").
(When logged in, completion status appears here.)