Is the time complexity for string comparison O(n) or O(1)?
Is the Big O time complexity for string comparison O(n) or O(1)?
O(n) and O(1) are from Big O Notation; which is used to describe the complexity of algorithms, and how their time/space performance scales with the input size.
O(n) represents a linear growth of operations with the size of the input, like climbing stairs step by step.
On the other hand, O(1) represents when operations remain constant, unaffected by the scale of the input.
But in which does string comparison lie? Particularly when the strings are unbound and random.
What is the complexity of checking whether one string is equal to another?
What does the programming community say?
ChatGPT and Leetcode say string comparison is O(n); in JavaScript and Java at least:
ChatGPT | Leetcode |
Been having this argument on social for the last few weeks since I posted a coding challenge involving it..
Some responded that it is O(1) for different reasons such as language/compiler optimizations.
Others responded that it is O(n) because when the strings compared are the same length, every character must be individually checked.
DSA pros please help.. 🛟
Final answer
I personally think it is indeed O(n) because…
🟡 In the best case, the strings are different lengths, and only the lengths need to be checked; which is O(1) / constant time complexity.
🔴 BUT in the worst case, when the strings are the same length, every character must be checked one-by-one to find if the strings are different, which is O(n) / linear.
🟢 Since Big O Notation resolves to the worst case, therefore the whole algorithm is O(n) in time complexity.
Final answer: O(n) time complexity
Let me know what you think though!