0

If I have an algorithm and part of it has a known worst case numerical value, which is reasonably small compared to the rest of the problem, is it ok to argue that part as O(1)?

E.g. If part of the algorithm involves building a linked list of characters out of a string, where the string may contain each of the ASCII characters at most once, I know that the worst case is building a linked list of 127 nodes from a string that is 127 characters long. Is it ok to argue that part as O(1)?

  • 1
    Formally, if it is bounded, it is O(1). But whether you do depends on why you are analysing it—the more fine-grained behaviour might matter or not. – Jan Hudec Sep 6 '17 at 10:59
  • One could argue that the limit imposed by the “ASCII characters” domain is not fundamentally part of the algorithm, and that other character systems could be used as well – consider what happens if the string consists of Unicode code points instead. – amon Sep 6 '17 at 11:13
  • With that one could argue that strlen is O(1) in practice – Sopel Sep 10 '17 at 9:49
3

Yes, as soon as an absolute upper bound is known the algorithm has constant complexity.

Algorithmic complexity is only concerned how the algorithm scales for arbitrarily large input sizes: how long does it take for ten, thousand, and a trillion elements? Since your algorithm is only defined up to a certain maximum size, this scaling is not very relevant.

When analysing Big-O complexity, this maximum-input argument is often very convenient. For example, we generally assume that multiplication and addition are O(1) operations. But that only holds for fixed-width data types which are often sufficient in practice. It does not hold for arbitrary-precision/bignum operations, where addition would have O(log n) complexity (or O(n) to the number of bits).

It is not always OK to entirely ignore Big-O even when there's a maximum size. If the algorithm shows significant scaling properties within the domain where it's defined, that should be subject to analysis. For example, O(exp n) algorithms might be infeasible for anything but single-digit input sizes, so an upper limit in the thousands is completely irrelevant as it will never be reached. Similarly, the argument that all programs are O(1) because real computers have finite memory and are therefore bounded is specious: you're usually going to feel the effects of Big-O long before you hit that limit.

1

No, I would not accept a (low) bound on the possible inputs as an argument for calling that part O(1).

On the other hand, if this is part of a larger algorithm that does not have the same bound on the worst-case input, then the total algorithm is O(f(N)*g(M)) where f(N) is the complexity of the part that has a bounded worst-case input and g(M) is the complexity of the other part.
Now it can be argued that for large M, the g(M) part dominates the overall complexity and the effect of the bounded-input part can be neglected for further analysis.

0

It depends on who is reading this. Computer Science is usually concerned with asymptotic cases. But in your case, you seem to have O (n) where n is the number of possible different characters, and you artificially restrict n to 128 by choosing ASCII and claim it's O (1). Well, I'd want to handle at least the full Unicode range (about a million code points), and probably extended grapheme clusters, which are unlimited, so I'd find this very unsatisfying.

In Software Engineering, we usually are concerned with how fast it runs in practice. If you do k operations, and each operation is a loop over 128 ASCII characters, that will have an effect on the runtime, and people may consider you cheating.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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