system
Given the following post, respond as if you're commenting on Reddit:
human
Big-O-Notation Confusion

I've read multiple sources on the subject and while I get the general idea of Big-O-Notation, there are certain things about Big-O-Notation that don't make sense and which lead me to doubt my understanding of the concept. 

For example, my textbook says to "Note that for small values 
of n, the exponential function is smaller than all of the others. As shown, it is not until n reaches 20 that the linear function is smaller than the quadratic".

But for f(n), f(20) = 20, while for f(2^n), f(2^20) = 1048576. So what the hell? Last time I checked, 1,048,576 is greater than 20.

Something else I don't understand is if you have 100 simple statements that do the same thing, that's equivalent to having a for loop that executes one of those statements 100 times. But we say the simple statements have a complexity of O(1) while the for loop has a complexity of O(n), implying that, in general, the O(1) takes less time than the O(n). But they do the same thing, so how is that supposed to make any sense at all?

Is this because checking conditions in the loop takes time? If that's the case, why does nobody bring this up??? It's confusing as hell.
gpt
I think there are a couple of different things you're confused about.

For one thing, the *exponential* function f(n)=2^n is different from (and grows much faster than) the *quadratic* function f(n)=n^(2).

Secondly, big-O is used to talk about *functions*, not numbers. A function takes some input value, and describes a quantity that varies according to that parameter. When we're talking about time complexity. we're interested in how the running time changes in terms of the *size* of the input -- using whatever definition of "size" makes the most sense for the particular problem.

If you have a for-loop that runs from i=1 to i=100, but the bound is always 100 no matter what the input looks like, then the time complexity is O(100) = O(1). On the other hand, if it takes as its input an array of length N, and the loop runs from i=1 to i=N, then the time complexity is O(N).

Finally, if you want to talk about specific values where one function becomes larger than another, you have to be specific about which function you're talking about. The functions f(n)=n^(2), f(n)=2n^(2) and f(n)=100000n^(2) are all "quadratic" -- they fall into the complexity class O(n^(2)) because their fastest-growing term is proportional to n^(2). But they would intersect any given linear function in very different places. The diagram in your book is showing *examples* of functions in different categories, with constants chosen to let you compare their shapes.

The reason big-O notation is useful is because it allows us to *not worry* about the exact constant values, because we know that *eventually* the faster-growing function will outgrow slower-growing ones. The mathematical definition of big-O is basically just a rigorous way of defining what "eventually" means.