We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.

O(1) means that this method runs just as fast on n = 1,000,000,000 as it does on n = 10, which isn't the case. The string multiplication is the performance bottleneck causing the algorithm to be O(n) rather than O(1). Here's some test code showing that the code is O(n) due to the string() call (I'm not a C++ programmer, so pardon any mistakes):

My main point is that a lot of folks are mistakenly assuming the while loop solution is not O(1). The loop in this case is O(1) because regardless of how large n is, the loop body will never execute more than twice at most, so from an efficiency standpoint there is no difference as advertised. See the below code:

You are right, there is a but. The author of Editorial and other people simply neglect "multiplying strings" and other operations because the performance difference in comparison with the Sherlock algorithm O(1) is extremely small at the level of 1 <= n <= 100000.

## Sherlock and The Beast

You are viewing a single comment's thread. Return to all comments →

O(1) means that this method runs just as fast on

`n = 1,000,000,000`

as it does on`n = 10`

, which isn't the case. The string multiplication is the performance bottleneck causing the algorithm to be O(n) rather than O(1). Here's some test code showing that the code is O(n) due to the`string()`

call (I'm not a C++ programmer, so pardon any mistakes):My main point is that a lot of folks are mistakenly assuming the while loop solution is not O(1). The loop in this case is O(1) because regardless of how large

`n`

is, the loop body will never execute more than twice at most, so from an efficiency standpoint there is no difference as advertised. See the below code:You are right, there is a but. The author of Editorial and other people simply neglect "multiplying strings" and other operations because the performance difference in comparison with the Sherlock algorithm O(1) is extremely small at the level of 1 <= n <= 100000.