this post was submitted on 22 Jun 2024
403 points (97.4% liked)

Programmer Humor

19817 readers
555 users here now

Welcome to Programmer Humor!

This is a place where you can post jokes, memes, humor, etc. related to programming!

For sharing awful code theres also Programming Horror.

Rules

founded 2 years ago
MODERATORS
 
you are viewing a single comment's thread
view the rest of the comments
[–] [email protected] 14 points 6 months ago (3 children)

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.

[–] [email protected] 16 points 6 months ago (1 children)

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.

[–] [email protected] 2 points 6 months ago

Spot on. Good explanation.

[–] [email protected] 5 points 6 months ago

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.

[–] [email protected] 1 points 6 months ago (1 children)

lim n->inf t(n) <= O*c, where O is what is inside of big O and c is positive constant.

[–] [email protected] 1 points 6 months ago (1 children)

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.

[–] [email protected] 2 points 6 months ago* (last edited 6 months ago)

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.