why does it seem like nobody understands what big O notation actually is
Sex with anthro women
your mom reached big o in constant time
sounds like a problem for the vibe coding LLM to worry about frfr.
>>108892034me on the left
something sometheing big o deez nuts
>>108892034Dorothy is love, Dorothy is life
>>108892034Good question. It's a simple mathematical definition that fits in one line. Yet for some reason nobody seems to grasp the definition or simply not care about it, and constantly say wrong things about big O notation.
>>108892034I don't understand. Are you implying that big O applies to dating in some way?
This is chatGPT 5.5 thinking wrongly claiming that array access at an index is not an O(n^2) operation
Fun fact: derivatives can be formulated in terms of big O/small o notation.A function f has a derivative at x if and only iff(x + h) = f(x) + f'(x)h + o(h)or f(x+h) = f(x) + f'(x)h + O(h^2)for some f'(x) (uniquely determined by this equation).This allows us to simply prove a lot of the properties of derivativesFor example chain rule:f(g(x+h)) = f(g(x) + (g'(x)h + o(h))) = f(g(x)) + f'(g(x)) (g'(x)h + o(h)) + o(g'(x)h + o(h)) = f(g(x)) + f'(g(x))g'(x)h + o(h)thus (f o g)' = f' o g * g'
>>108893873With big O notation it's very similar actually.f(g(x+h)) = f(g(x) +(g'(x)h + O(h^2)) = f(g(x)) + f'(g(x)) (g'(x)h + O(h^2)) + O( (g'(x)h + O(h^2))^2 = f(g(x)) + f'(g(x))g'(x)h + O(h^2) becauseO( (g'(x)h + O(h^2))^2 belongs to O(h^2).
>>108893841Looks like chatgpt is ready to replace (You).
>>108893926I realized that it's likely nobody understands the post so I feel like I need to clarify. I am saying that chatgpt is retarded.
>>108893841oh you're that faggot again.
>>108892261are you trans
>>108893930An array is contiguous memory block so it’s O(1). The only time you’re going to get O(n^2) is when you have array indices within nested loops.
>>108893943At least explain to him why he’s retarded so he can learn.
>>108894053You didn't get it I see.All O(n) programs are also O(n^2), which are all O(n^3), etc. The answer to OP's question to chatgpt was "true" because of the definition of big-O. You are proving OP's point.
>>108892034My first year algorithms professor told us "this isn't actually completely correct but it'll be more useful to you than the full definition" when he first explained big O. I assume we got the engineer version, like how the engineer version of calculus lets us use dx and dy as if they were separate variables.
>>108894103You’re technically correct, you’re just being a pedantic fuck about the mathematical definition. In actual engineering discussion people use the tightest meaningful bound, otherwise every linear algorithm is also O(n^2), O(n^3), O(n^999), etc. which makes the notation basically useless for communicating real world performance.
>>108894125>like how the engineer version of calculus lets us use dx and dy as if they were separate variables.That's just how math works retardt. pure math grad
>>108894145>In actual engineering discussion people use the tightest meaningful boundWrong. The tightest meaningful bound is always the function itself. Yet in actual engineering discussion people use different function than the function itself.>which makes the notation basically useless for communicating real world performance.Wrong.
>>108894145That was OP's point though. This is why chatgpt is wrong and why OP was right to say people don't seem to understand big-O notation.There are other notations for other kinds of bounds, like big-omega and little-o notation. Sometimes it's not obvious what the tight bound is, but it is useful to be able to express as a polynom that is clearly higher than the actual execution. Thus, you can say the algorithm is O(n^2) when actually it's tighter if you do the whole math about it. This allows for analyses that otherwise aren't tractable. You are arguing that nobody uses a hammer to punch in a screw, which is of course true, but forget that there are other tasks one might do with hammers.
Posting the classic wrong explanation where every other sentence is wrong.
>>108894153You’re arguing from formal mathematical permissibility while I’m talking about practical engineering communication. Nobody in normal performance discussion calls a linear algorithm O(n^2) just because it technically satisfies the upper bound definition. The point is communicating useful scaling characteristics, not winning a theorem debate.
>>108894147No it doesn't and yes it does. It certainly doesn't work that way for naive calculus (n-th derivatives break), though for more technical definitions (dx, dy as basis of the cotangent space of R2) it does kind of work.>>108894103You are expecting rigurosity in engineering, it's such a non-issue thing to nitpick.
what a productive use of time this thread was
>>108894466Wrong.
Okay /g/, are you smart enough to solve this?I think this will be a good question to filter people who understand big O from the people that don't
>>108894466I mean, the long short of it is we're arguing over technical definition on a relatively niche subject only autistes in the industry give a shit about and FAGMANs sort of pay lipservice to which is stupid, but compared to the other boards debating on waifus, vidya, shitcoin gambling, how to be an effective wignat and maintain a good relationship with your black gf, and some guy called nobody and esoteric cum magick... Yeah, I'd say it was fairly productive.
>>108894583''Spoiler:''{{f \in O(g) \quad \text{but} \quad g \notin O(f)}}
>>108894583|7x+3| <= c |x^2| given domain in both cases is Z+ === (7x+3) <= c(x^2) -> 3/(c-7) <= x which satisfies f in O(g).In case 2: (a+1)^2 - a^2 <= c (7(a+1)+3) - c (7a+3) -> 2a+1 <= 7c. Contradiction.
CAST IN THE NAME OF GODYE NOT GUILTY
>>108892045This
>>108892034then explain it correctly retard
Why do people still have to figure out the O-ness of functions by hand? Why can't it be programmatically inferred so that IDE could slap an annotation for each function and have it update real-time as you edit?
>>108895747Halting problem. However there are solutions that can make good estimates on the big-O. They're researchware though. Also, halting problem is widely a meme. It's perfectly acceptable to say 'I know this" vs "I don't know this", i.e. the vast majority of subprograms are totally determinable. There's nothing wrong with simply rejecting to analyse the others.
>>108895767Couldn't you just restrict the analysis to a local scope which you know can halt, and compose that knowledge? I'd imagine even the subset of known behavior is more useful than not having anything at all.
>>108895812That's what I'm suggesting, yes. The problem is that anytime someone suggests implementing such features, people scream about muh halting problem and nobody tries.
>>108894645Scientifically speaking, you are neglecting the discussions on 0.999.... = 1 and that whole thing with the car and the goats.
>>108895819That's stupid man. The tooling in this profession is so primitive it hurts. We could have the editors annotate so much more shit we try to keep in our heads.
>>108895856Even beyond the fact we could have all kinds of useful automated analysis that isn't happening yet, even automated annotation of things that already have tools for it (static analysis and such) is severely lacking/integrated in current workflows, and we've lost the ability to do mix compiled languages with RAD capabilities, error management mechanisms in modern languages are a joke compared to what we had, etc. etc.Everything sucks, but the worst part is that there already are a shitton of non-sucky alternatives, we're just not allowed to have them for some fucking reason.
>>108892034People are implicitly using the lowest form of big o that gets satisfied, because it is more useful and also communicates every larger form that it satisfies. You would have to be some retard to not understand this.
Why do women love cutting? What's the point of that
>>108896144Women are not human, they're unable to think. Or love for that matters. They just "are", like plants or rocks.
Reminder that nobody asked for a mathematician's opinion on what O(n) means. O(n) means the lower bound. Get used to it or get a refund on your useless degree.
Nobody cares, it's not the 90s gramps move on computers are faster now
Well. I am currently reading Knuth's Art of Computer Programming, and I am on this section, so this thread is rather timely. I always thought that O notation was a way to describe the performance of an algorithm, but from this text, it's actually a way to quantify a degree of accuracy/approximation?
>>108893888>>108893873I should have got a math degree instead of this useless fucking CS degree
>>108897429You're not smart enough to have passed a math degree's curriculum. Nobody who chooses to go into CS is.
>>108895964>People are implicitly using the lowest form of big o that gets satisfiedThis is wrong.
>>108892045The lack of this is the critical difference between proving P=NP and people not understanding big O notation.
>>108897402It's both. When you have a complicated expression in your analysis such as n^3log(n)^2 + n^4 you often dont really care about what it is exactly and to save mental space you just replace it with O(n^4) which is much simpler to keep track of. You know it mean some some term that doesn't grow much faster than n^4, but you don't necessarily know how fast.This allows you to go much further in your analysis than you typically would by saving space and effort.
>>108893873That's just taylors theorem
>>108897429What the other anon said. Just felt like restating it.
>>108897402Dandelion souply, speaking Bachmann-Landau is "just" a thin category with strict-order refinement.
I know what it is, I just don't know how the fuck I'm supposed to know what an algorithm ends up being (unless it's trivial).
>>108892034why does it seem every time i come on this board there is ANOTHER BORING THREAD about the *Technically Correct* definition of something (which is of absolutely no use or interest to anyone) and how the 99.9999999% of people who use it for something they find useful and practical are all wrong and should stop.however there is never any advice or instruction about what alternative should be used?curious.probably because its just a troll thread from the guy whos big idea is saying that 2 = 2 implies that 2 != 1 which is wrong because 2 > 1. if its that shit again then i just do not care at all dont reply to me i dont care
>>108898461You decompose the algorithm into parts that are trivial.
>>108897899>This is wrong.This is wrong.
>>108892034>the biggest hurdle of a CS jeet is big OGreat thread anon.
>>108892034Because most programmers don't know basic math
>>108892034>f(n) = O(g(n))this shitty notation doesn't even make sense, it should be something like "f(n) ∈ O(g(n))"
>>108892034It's anime batman or some shit I think.
>>108897437There was a time when a CS degree paid more than a math degree and you only got that because of autism and to flex.
>>108892261That drawing isn't you, retard
>>108894927kek
>>108899696I was told that's another way to write it but for convenience we chose =
isnt that just rate of change between input and output
>>108902281No, what you're thinking of is a derivative.
>>108892034It was only talked about in one of my classes, and all I remember is enough to explain to people how some problems are just too complex to solve in a reasonable amount of time.
>>108904521i was thinking of asymptotics and apparently that's literally what O notation is
