41–50 of 168 posts
I propose limits. I think it would be a lot easier for someone to understand how to think about big-O if they already understood limits.
Lim [x -> inf] O(f(x))/O(g(x))
If you know limits, you know you how and why you can ignore all but the highest power term, how to compare and simplify other kinds of terms, etc. Though maybe that's too much to ask of someone new.
Earlier quoted context omitted.
Admittedly I am studying theoretical physics so I am supposed to be able to, but it made sense to me?
Excellent! The level I was shooting for with my brief explanation was that someone who understood limits at a calc 1 level should be able to get it with a little thinking. I do wonder, though: did you know those things before you read my comment?
Ultimately you're limited in not having graphs, which always limits the intuitiveness of any calculus-explainers.
If you really want to make it easy to understand, make it graphical. That is: benchmark the code, varying the input size, and plot the results. Almost anyone should be able to understand. This might also reveal effects that are not taken into account by Big O notation, as not all algorithms that have the same complexity have the same performance. But I see it as a plus.
Also amortized analysis, e.g. appending to a std::vector is O(n) in the worst case but O(1) almost all the time (the O(n) spikes come at something like every n = golden_ratio^k * initial size for integer k)
Earlier quoted context omitted.
So what would be a deceptivly simple unsolved problem?
Wikipedia has a list of big-name unsolved problems in complexity theory. Most of these have very simple problem statements. https://en.wikipedia.org/wiki/List_of_unsolved_problems_in_c...
Earlier quoted context omitted.
Excellent! The level I was shooting for with my brief explanation was that someone who understood limits at a calc 1 level should be able to get it with a little thinking. I do wonder, though: did you know those things before you read my comment?
I did. For some scale of what I get up to I'm currently banging my head against various differential geometry textbooks. Ultimately you're limited in not having graphs, which always limits the intuitiveness of any calculus-explainers.
If I were writing this as a web page, though, I would definitely include a few graphs to explain the calculus concepts. The amount of calculus you need here is pretty intuitive once you draw a couple of pictures.
>> If you consider "addition" to be 1 operation then ... What if we don't? Addition on computers is an O[1] operation only because we use fixed bit-widths for numbers, e.g., a 32-bit signed integer. How would we reformulate or express algorithmic complexity if we were to talk about unbounded integer values or infinite-precision mathematics?
The computational model of a book like CLRS is "arithmetic is O(1), but we're not going to abuse that bug".
Count the number of nested loops. If one of the loops does splitting (like binary search) it’s a O(log n) as opposed to O(n). That’s literally all there is to it.
Strassen algorithm is 7-multiplications for a 2x2 matrix. https://en.wikipedia.org/wiki/Strassen_algorithm A matrix can always be split into groups of sub-matrix, and the groups of sub-matrix is itself a matrix. Applying Strassen algorithm recursively is therefore O(n^log2(7)) == O(n^2.8ish).
>> If you consider "addition" to be 1 operation then ... What if we don't? Addition on computers is an O[1] operation only because we use fixed bit-widths for numbers, e.g., a 32-bit signed integer. How would we reformulate or express algorithmic complexity if we were to talk about unbounded integer values or infinite-precision mathematics?
Gauss-Jordan is O(n^3) if you consider addition and multiplication to be constant-time, but if it operates on arbitrary-precision integers, it can get exponentially slow[2].
The Bareiss algorithm avoids this worst-case behavior by choosing the pivots in a slightly more involved manner, which avoids building up large intermediate values.
[0]: https://en.wikipedia.org/wiki/Gaussian_elimination#Computati... [1]: https://en.wikipedia.org/wiki/Bareiss_algorithm [2]: https://staff.itee.uq.edu.au/havas/fh97.pdf, Section 3.1's "Construction A" is a specific matrix that exhibits the worst-case behavior.
Earlier quoted context omitted.
I did. For some scale of what I get up to I'm currently banging my head against various differential geometry textbooks. Ultimately you're limited in not having graphs, which always limits the intuitiveness of any calculus-explainers.
Cool. Sounds like you're in grad school right now, yeah? I know differential geometry is not exactly the same as differential topology, but I remember taking differential topology in grad school. I was always amused that we never actually evaluated any integrals that didn't come out to a very simple number (generally 0). If I were writing this as a web page, though, I would definitely include a few graphs to explain…