1
$\begingroup$

This question already has an answer here:

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?

$\endgroup$

marked as duplicate by Barry Fruitman, Yuval Filmus algorithms Jul 25 '17 at 21:36

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ There is no such thing as "real-world complexity". Case closed. $\endgroup$ – Raphael Jul 25 '17 at 17:26
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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}$.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.