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:
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 onn = 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 thestring()
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: