Let's say an algorithm has an asymptotic time complexity of $\Theta(N)$. However in practice, $N$ is bound by a small upper limit (e.g. the size of a character set). Can we then say the complexity is $\Theta(1)$? Or is there a better way of describing the performance of an algorithm in a particular real-life situation?
$\begingroup$
$\endgroup$
1
asked Jul 25, 2017 at 16:49
-
$\begingroup$ There is no such thing as "real-world complexity". Case closed. $\endgroup$– RaphaelCommented Jul 25, 2017 at 17:26
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
If $N$ is bounded by a small upper limit, asymptotics cease to be useful. At that point you want either exact operation counts, or even better just measure actual speed.
$\begingroup$
$\endgroup$
Keep in mind algorithms do not know the input before they receive it. Algorithms are (typically) blind in that regard.
For example, if you have an algorithm that computes something about an alphabet of size $n$, the algorithm doesn't know that your alphabet may be restricted to 26 characters, or all ASCII characters, or all unicode characters. The algorithm only knows that it will receive $n$ characters and compute something about them. The algorithm would then still take an amount of operations as a function of $n$, not $O(1)$ necessarily.
With that being said, if you have hard coded in the algorithm that the input is only the size of a particular alphabet you could then argue that it actually is $O(1)$. Although, I would then argue that it's not a valid solution for all alphabets, but you might not care if it does solve your problem. Even if you do have the input size upper bounded, it can still be good to represent it as a function of $n$ while specifying the upper bound as well. For example, if I know my input size is upper bounded by $2^{32}$, then sure the algorithm runs in $O(1)$, but that's not going to be helpful to anyone. It'd be better to say it runs in $O(f(n))$ until an upper bound of $n \leq 2^{32}$.
