After all these years I still don’t know how to look at what I’ve coded and tell you a big O math formula for its efficiency.
I don’t even know the words. Like is quadratic worse than polynomial? Or are those two words not legit?
However, I have seen janky performance, used performance tools to examine the problem and then improved things.
I would like to be able to glance at some code and truthfully and accurately and correctly say, “Oh that’s in factorial time,” but it’s just never come up in the blue-collar coding I do, and I can’t afford to spend time on stuff that isn’t necessary.
A quadratic function is just one possible polynomial. They’re also not really related to big-O complexity, where you mostly just care about what the highest exponent is: O(n^2) vs O(n^3).
For most short programs it’s fairly easy to determine the complexity. Just count how many nested loops you have. If there’s no loops, it’s probably O(1) unless you’re calling other functions that hide the complexity.
If there’s one loop that runs N times, it’s O(n), and if you have a nested loop, it’s likely O(n^2).
You throw out any constant-time portion, so your function’s actual runtime might be the polynomial: 5n^3 + 2n^2 + 6n + 20. But the big-O notation would simply be O(n^3) in that case.
I’m simplifying a little, but that’s the overview. I think a lot of people just memorize that certain algorithms have a certain complexity, like binary search being O(log n) for example.
Time complexity is mostly useful in theoretical computer science. In practice it’s rare you need to accurately estimate time complexity. If it’s fast, then it’s fast. If it’s slow, then you should try to make it faster. Often it’s not about optimizing the time complexity to make the code faster.
All you really need to know is:
Array lookup: O(1)
Single for loop: O(n)
Double nested for loop: O(n^2)
Triple nested for loop: O(n^3)
Sorting: O(n log n)
There are exceptions, so don’t always follow these rules blindly.
It’s hard to just “accidentally” write code that’s O(n!), so don’t worry about it too much.
Here is a picture, that may help a little bit. The n is input size, and f(n) is how long does the algorithm runs (i.e how many instructions) it takes to calculate it for input for size n, i.e for finding smallest element in an array, n would be the number of elements in the array. g(n) is then the function you have in O, so if you have O(n^2) algorithm, the g(n) = n^2
Basically, you are looking for how quickly it grows for extreme values of N, while also disregarding constants. The graph representation probably isn’t too useful for figuring the O value, but it can help a little bit with understanding it - you want to find a O function where from one point onward (n0), the f(n) is under the O function all the way into infinity.
After all these years I still don’t know how to look at what I’ve coded and tell you a big O math formula for its efficiency.
I don’t even know the words. Like is quadratic worse than polynomial? Or are those two words not legit?
However, I have seen janky performance, used performance tools to examine the problem and then improved things.
I would like to be able to glance at some code and truthfully and accurately and correctly say, “Oh that’s in factorial time,” but it’s just never come up in the blue-collar coding I do, and I can’t afford to spend time on stuff that isn’t necessary.
A quadratic function is just one possible polynomial. They’re also not really related to big-O complexity, where you mostly just care about what the highest exponent is:
O(n^2) vs O(n^3).For most short programs it’s fairly easy to determine the complexity. Just count how many nested loops you have. If there’s no loops, it’s probably
O(1)unless you’re calling other functions that hide the complexity.If there’s one loop that runs N times, it’s
O(n), and if you have a nested loop, it’s likelyO(n^2).You throw out any constant-time portion, so your function’s actual runtime might be the polynomial:
5n^3 + 2n^2 + 6n + 20. But the big-O notation would simply beO(n^3)in that case.I’m simplifying a little, but that’s the overview. I think a lot of people just memorize that certain algorithms have a certain complexity, like binary search being
O(log n)for example.Spot on. Good explanation.
Time complexity is mostly useful in theoretical computer science. In practice it’s rare you need to accurately estimate time complexity. If it’s fast, then it’s fast. If it’s slow, then you should try to make it faster. Often it’s not about optimizing the time complexity to make the code faster.
All you really need to know is:
There are exceptions, so don’t always follow these rules blindly.
It’s hard to just “accidentally” write code that’s O(n!), so don’t worry about it too much.
lim n->inf t(n) <= O*c, where O is what is inside of big O and c is positive constant.
Basically you can say that time it takes never goes above grapf of some function scaled by constant.
Fun side effect of this is that you can call your O(1) algorithm is O(n!) algorithm and be technically correct.
Here is a picture, that may help a little bit. The n is input size, and f(n) is how long does the algorithm runs (i.e how many instructions) it takes to calculate it for input for size n, i.e for finding smallest element in an array, n would be the number of elements in the array. g(n) is then the function you have in O, so if you have O(n^2) algorithm, the g(n) = n^2
Basically, you are looking for how quickly it grows for extreme values of N, while also disregarding constants. The graph representation probably isn’t too useful for figuring the O value, but it can help a little bit with understanding it - you want to find a O function where from one point onward (n0), the f(n) is under the O function all the way into infinity.