[tyilo]

The first thing to note that, given a deterministic program that computes a boolean given an infinite bit string will either run in O(1) time for all inputs or will have an input where it doesn't halt.

Thus if you assume that the function is total and thus doesn't halt, it must run in O(1) time.

To find an infinite input bit string where the function halts, we can just record which k = O(1) bits the function is querying and then try all 2^k possibilities and as calculating the function is O(1) the total time is also O(1). (We don't always have to try all 2^k possibilities).

[tempodox]

How is not halting O(1)? Wouldn't that be O(∞)?

[scapp]

I think they meant

> Thus if you assume that the function is total and thus does halt, it must run in O(1) time.

Since that's what total means.