Θ Abstracts Away the Choice of n (Mostly)
Remember for \( \mathrm{C}_{\mathrm{index}} \) we used the number of input bits for \( n \) and for other ones we used the size of the array?
Yeah, sure. What about it?
-
Well, which one should we use?
-
Great question! Asymptotically… it doesn't matter!
We decided that \( \mathrm{C}_{\mathrm{index}}(n) = \frac{ n - 128 }{ 32 } \), where \( n \) is the number of bits in the array and all three parameters.
Sure it is:
\[ \begin{align} \lim_{n \to \infty} \frac{ ( \frac{ n - 128 }{ 32 } ) }{ n } & = \lim_{n \to \infty} \frac{ n - 128 }{ 32n } \\ & = \frac{1}{32}. \end{align} \]
We could likewise say that \( \mathrm{C}_{\mathrm{index}}(n) = n \), where \( n \) is the number of elements in the array. And hopefully we agree that \( n \in \Theta(n) \).
So they're both \( \Theta(n) \).
-
Ah, so either way, we can see that it takes linear time!
-
That's right!
Does that mean we can choose any quantity for \( n \)?
-
No, definitely not.
A Rule of Thumb for \( n \)
The most typical notion of what \( n \) should be is the description length of the input. The description length is the number of bits needed to write down the input to the algorithm.
-
We were basically doing that when we used the number of bits in the array and the three parameters!
-
That's right!
-
So, why is it okay to use the number of array elements instead?
-
Well, remember that constant factors and lower-order terms don't matter in the limit…
In this case, the number of bits for the parameters is the same for every input (128), so that's a lower-order term.
The number of bits in the array is a multiple (32) of the number of elements in the array. So the number of bits per element is a constant factor.
Since \( n \in \Theta( 32n + 128 ) \), the number of elements in the array is the same order as the description length of the input.
As a result, for the purposes of asymptotic analysis, the number of array elements is just as good a choice as the description length!
Where things can go wrong is if you start interpreting \( n \) to be a quantity that is not of the same order as the description length.
-
For instance, if we had gotten confused and let \( n \) be the number of bits in the parameters without the array, then our analysis would have been very strange.
-
But still, when we say \( \Theta(n) \), we don't necessarily have to be super specific about what \( n \) is. It is presumed to be something on the order of the description length of the input.
-
All that said, when we ask you to do analyses, we will often specify, just to be sure we are all on the same page!
(When logged in, completion status appears here.)