Hacker News Reader

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

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

It’s O(log n) … probably :-)

for almost all inputs

Amortized :-)