3 ms·

Presumably it's impossible to state what the big-o of a checking algorithm is since it's not proven to halt?

• deleted 5y ago
  [deleted]
• mcphage 5y ago
  It’s O(log n) … probably :-)
  • handol 5y ago
    for almost all inputs
    • mcphage 5y ago
      Amortized :-)
• AnotherGoodName 5y ago
  The video stated that on average the number is multiplied by 3/4 on each step. Solve initial_value * (3/4)^x = 1 for x to get the number of steps. That'll give a logarithm. So yes it's O(logn) on average