A visual introduction to big O notation

Having gone through electrical engineering, I always felt that Big O notation was never properly explained unless I happened to miss every time it was introduced. It always felt like it was just hand waived as something we should already know. I'm curious what level of math or computer science is usually responsible for introducing it.

That’s because you could define it in a lot of different ways. For example, if you define it as the number of steps it takes some Turing machine representing some algorithm to halt, then there is no such thing as a logarithmic time algorithm; O(lg n) = O(1)

Why is that?

Log(n) grows slower than n. That means there is some number N where the process terminates in fewer than N state transitions. But in a Turing machine, you can read at most one new cell on the tape with each state transition. Therefore the algorithm halts in constant time.

What is the relationship between n and N? log(n) is still unbounded so I can’t make sense of your comment.

There is no relationship between n and N, of course. N is some fixed constant.

Log(n) is unbounded, yes, but if a Turing machine halts in sub-linear time then there is some length input for which that TM halts before it reads every cell of the input tape. Therefore, it doesn’t matter how the size of the input grows, that TM must halt in constant time. Make sense?

I’m sorry but no. Maybe it’s my ignorance of TM’s, but O(log n) doesn’t read all input by definition. It doesn’t follow that it is therefore _independent_ of the input size.

What makes a/your TM special that this is the case?

I don’t mean to take too much of your time though, maybe I’m too dumb for this.

Edit: I can sort of see how O(log n) is impossible or at least O(n) in a TM, but to reduce it to O(1) makes no sense to me