"Hard" is relative to prerequisite knowledge, which can vary significantly.
"Hard" is relative to prerequisite knowledge, which can vary significantly.
You drop the constant because it doesn't alter how the complexity grows as the input increases.
If it's not too intrusive, may I ask what your graduate degrees are?
This discussion is making me think that a good way to write a "Big-O explainer" would be sort of like a progressive web app, i.e. "here's the explanation with the highest level of mathematical sophistication. Click here to get some of the prerequisite knowledge." Then, the user just keeps clicking "break it down more" until either they get it or they reach the most detailed explanation.
Anyway you can show that on the spot if you think about what the derivative of that monomial looks like
I'm really not sure on this one. This is easy if you have an idea of: 1. how you can graph things (runtime vs input size) 2. do the same but stretching the function to infinity 3. compare this to some term (which isn't as tangible compared to most algorithms imo),
And this is only for the intuition part. For people that got into programming by doing some UI stuff, I can definitely can see why _a subset of people_ struggle with this.
So f(n):=3n+28 will be O(n^2), because choosing c as 3, for every n greater than or equal 4, 3n^2 will be greater than f(n).
It would help if I could draw some graphs, but hopefully it helps.
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 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.
>> f(x) is O(g(x)) iff there exists a positive number M and an x_0 such that for all x > x_0, |f(x)| <= Mg(x).
is fairly similar to the so-called epsilon-delta definition of limits of functions. This way of reasoning is quite common. I know I bumped into it quite a lot: I learnt it in high school, even though I really understood it a couple of years later (I did a MSc in Physics). So the explanation above makes sense even if I never saw this exact formulation. Now I appreciate that not everyone is a Physics graduate, but I’d expect this to be understandable for people with degrees in applied Maths, Physics, or some related engineering discipline.