Search code examples
big-ocomplexity-theoryanalysis

Complexity of scanning a bounded length string. O(n) or O(1)?

Suppose we have a string of unique ASCII characters, which means that its length will never exceed 128 characters.

If I am to scan this string, where scanning means performing a constant-time operation on every character, does this scan counts as O(n), or O(1)?

Where n is the actual length of the string.

Solution

  • The answer

    When asking for the time or space complexity of an algorithm in terms of n, you need to define what n is.

    A linear scan of an array of n characters has, as you know, a time complexity of O(n). Since you are applying this same algorithm to your array of <= 128 characters, you can definitely be correct in saying that you are applying an O(n) algorithm to your array.

    However, if you define the algorithm as "scanning through a character array of max 128 characters", then your algorithm will indeed have a time complexity of O(1) because its number of operations is upper-bounded by a constant.

    So to answer your question: It is a matter of perspective. How do you define your algorithm?

    • "A generalized scan of an array of length n"? Then it's O(n), where n in your particular application just so happens to never exceed 128 (good for you).
    • "A scan of 128 or fewer characters"? Then it's O(1), because its time is upper-bounded by a constant.

    Philosophizing a little further

    Now, even if you were to extend the length of your array to fill up all your RAM, however large, it is still a finite integer and therefore you would, mathematically, be completely correct in claiming that it will run in O(1) time. However! How relevant is it to define an algorithm which scans through an array which fits in your RAM? We have just severely diminished the usefulness of our algorithm, because if, say, I have more RAM than you then your algorithm will not serve my needs.

    This is why we use a parameter, n, to denote some metric (here the length of the array). This allows us to define a scanning algorithm which works for inputs of ANY(!) size. As you know, this algorithm is at best O(n), which may not sound as nice as O(1), but it is now a general algorithm which can be used for any input size as opposed to the one where we included the input limit as part of the algorithm itself.