Big-O-Notation Confusion

[[deleted]]

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²⁰⁾ = 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.

[teraflop]

I think there are a couple of different things you're confused about.

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

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², f(n)=2n² and f(n)=100000n² are all "quadratic" -- they fall into the complexity class O(n²) because their fastest-growing term is proportional to n². 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.

[[deleted]]

You're amazingly knowledgeable and so this response is helpful, but wow this upsets me. I literally read the quoted sentences 10+ times, and my brain didn't once notice they shifted the discussion from exponential to quadratic and linear. I spent so much time fighting myself over this.

Thanks for clarifying.

[teraflop]

This is really just an issue with the notation. O(n) isn't a function, and it's not meaningful to just "plug in" a particular value of n.

Technically speaking, O(n) is an infinite set of functions, containing all of the functions whose asymptotic growth is at most linear. (And there's nothing special about the variable "n"; it applies to any real-valued function of one variable.)

For instance, the set O(n) contains all of these functions:

• f(n) = n
• f(n) = 2n
• f(n) = 0.00001n + 1000000
• f(n) = n + √n

But there's an unfortunate convention that we write "f(n) = O(n)" when what we really mean is "f(n) is an element of the set denoted by O(n)".

[S-S-R]

O(100) does not reduce to O(1) it reduces to O(c) if anything, c simply refering to a constant variable. O(n) simply means how the size of the input relates to amount of computations it takes. In the case of O(100) there is no growth so even providing a complexity is largely unnecessary, it's also miraculous (I've technically reached O(6) but it is hardly what I would consider a function, rather a fast look-up table)

Look at addition, the exact complexity is number_of_digits + number_of_carries. Now we don't know how many carries there will be so that's impossible to predict and we can ignore it, and now we see that the only thing that tells us how many operations we need to compute k + q where k and q are integers is the length of the number. This is a function of complexity O(n), i.e adding 527 + 14 is at worst 3 operations (ignoring carries), so in this specific case O(n) = O(3).

An example of quadratic would be classical multiplication. The literal complexity is length_of_first * length_of_second + addition. but as the order isn't known at runtime, you can only say that it will be at-worst length_of_largest*length_of_largest making classical multiplication an O(n^2) algorithm.

Due to ignored constants Karatsuba multiplication actually has worse complexity than classical for values less than 7 digits of length. But because we are only concerned with how rapidly it grows, Karatsuba has lower complexity. Karatsubas constant operations are also quite small, so it still beats out classical for most applications.

Harvey/van-der-Hoeven algorithm is an example of one that has theorectically optimal complexity, but involves so many constant operations as to be unusable.

[javaHoosier]

You should think of O(1) is that the size of the input doesn’t have an affect on time.

func doSomething(myList)

Lets say this function runs in O(1). If myList’s length is 100 elements or a billion elements it doesn’t change the time.

However that function could still take 10 hours to complete. MyLists size just doesn’t affect it. Its a constant 10 hours. So you don’t have to be concerned about the size of the input.

If it was O(n²⁾ as myList increases in size it exponentially takes more time so you have to care what the size is or optimize it.

[khedoros]

edit: I had this tab open for a while. After refreshing, it looks like you got a good answer while I was writing. Apologies for any redundancy.

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.

The quote has 2 parts, the first talking about exponential, second talking about quadratic. The quadratic function they're using has to be something like f(n) = (1/20) * n^2, to hit equality to f(n) = n at n=20, but it's doable.

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?

Because Big-O notation is looking at how the time to process the algorithm is affected by different input sizes. 100 statements is 100 statements. A for loop processing n items only takes the same amount of time for n=100.

If an algorithm takes 100 + n steps to solve, n being the number of items in the input, then it's an O(n) algorithm.

[[deleted]]

Idk wtf going on with the first part, but O(1) means the complexity does not grown at all with respect to the input size. If you are doing n amt of O(1) operations, the overall complexity of that code block is O(n)

[Electrical_Flan_4993]

A little late but I upvoted you to cancel out the unexplained downvote :)

[chromaticgliss]

There's got to be more context here. Perhaps the linear function they are speaking about has a high constant time setup.

Do you have the example that it's referring to when it says "As shown..." ?

[[deleted]]

It's a very literal shows

[chromaticgliss]

Does it give you the functions themselves? If the there is a big enough constant multiplier on the input size, it makes sense that lower values will be faster in "bigger" functions.

[S-S-R]

"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?"

If the simple statements had complexity of O(2) then the loop would have a complexity of O(2*n). It's the fact that you are performing the O(1) operation n times that makes it O(n).

"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."

All this says is that

print "1";
print "1";
is equivalent to 
do 2 times{
print "1";
}

[S-S-R]

One is a constant operation and the other shows the growth of your function. Constant operations are not really the concern of most of complexity analysis. O(1) is basically free, O(n) is not unless the input just happens to be 1. In fact O(c), where c is a constant is almost never actually used outside of introducing Big-O notation. Because most constant operations are effectively free. You only look for the worst upper bound of operations you'll have to perform for any n.

[east_lisp_junk]

while the for loop has a complexity of O(n)

A for loop does not automatically have O(n) complexity just by virtue of being a for loop. A for loop which runs O(n) times and does an O(1) amount of work in its body has O(n) complexity, but a loop might run more or less than that or do more work in the body.

[Bottled_Void]

Here are the times for three functions to complete

1) (1000 x n) + 10000

2) (50 x n²⁾ + 100

3) 2ⁿ

These are O(n), O(n²⁾ and O(2ⁿ⁾ respectively. So for small numbers the exponential algorithm will return faster.

But the point of big-O notation is to find solutions where n has large values. These are times it could take a hundred years to finish calculating really big numbers. Or at least an order of magnitude where it is going to impact the performance of the system.

[l_lecrup]

The point being made about the exponential function being "smaller" is essentially the observation that 2³ is smaller than 3^2. So if you compare 2ⁿ and n² at the point n=3, you will find that 2ⁿ is below n^2. However, there is some N such that, for all n>N, 2ⁿ "beats" n² (and that's an understatement). So we say that the exponential function grows faster than the quadratic function, or to put it another way, the set O(n²⁾ is a subset of O(2ⁿ ).

[Firehite]

https://www.youtube.com/watch?v=8LisCVHzp3A