Sherlock and The Beast

  • + 0 comments

    The loop in this iterative approach will run at most 2 times, which technically makes this solution O(1) as well. However, it should be obvious that the direct formula will require fewer machine instructions. By counting just the math operations (so ignoring jumps, which inflate the cost even more), it breaks down like this (please comment if I made a mistake!):

    Direct (2 x N % 3):
      + 1 Multiply
      + 1 Mod
      = 2 Constantly
    

    Iterative:

     Best Case (N is divisible by 3):
      + 1 Comparison (  while(n > 0)  )
      + 2 Comparison and Mod  (   if(n%3 == 0)   )
      = 3
    
     Worse Case (N % 3 == 1), full loop runs twice:
       + 3 Comparison (  while(n>0)   )
       + 6(3x2) Comparison and Mod (  if(n%3 == 0)  )
       + 2(2x1) Subtraction  (  n -= 5  )
       = 11
    

    And we might as well do the 3rd case (loop runs once):

       + 2 Comparison (  while(n>0)  )
       + 4(2x2) Comparison and Mod (   if(n%3 == 0)  )
       + 1 Subtraction (  n -= 5  )
       = 7
    

    Since each case is equally likely, we calculate that the average cost is (3+7+11)/3 = 7 instructions.

    So although both solutions are O(1), we can correctly conclude that the iterative approach is ~3 times more expensive. If we counted jumps and assignments, it's more like ~4 times. This is a significant difference.