Earlier quoted context omitted.
Factorization of arbitrarily large numbers? I doubt it.
Yes.
On constant-size hardware?
And doesn't getting the data in and out already take O(N)?
Big O Notation – Explained as easily as possible
91–100 of 168 posts
Re: Big O Notation – Explained as easily as possible
#92I'll admit I'm a little surprised to see a topic like this get much attention. Have programming courses & curriculums changed so much in the past ~20 years that this isn't simply part of every introduction to the subject? Yes, the topic of code performance as a whole is more complex than just Big O, but as its own concept it was, in my time (get off my lawn!) pretty effective covered everywhere, and certainly the mom…
I think this might be for the self taught crowd of developers who never formally took Comp Sci, yet, who are also wielding important positions in software development that pay as well if not more than the guys who did take comp sci. You'd be astounded how big this self taught cohort could be and how much power they wield. They do their job pretty well, and yet, the basics of computer science is something that they ne…
I was dropped into the tech lead position at my job last year; I started in game design at art college, so having to run and gun has been fascinating. I'd be lying if I said I wasn't scared reading about much of the stuff in this comment section that really should be bread and butter.
I'm talking to my boss to see if there's some kind of training program I can pick-up on the side to help me gather what should be the basics that I've missed out on, although we're so overloaded finding the time and money is challenging. I'm lucky it's mostly CRUD, but I can't help by worry every architecture decision I'm making is going to cost us massively down the road.
Re: Big O Notation – Explained as easily as possible
#93I'll admit I'm a little surprised to see a topic like this get much attention. Have programming courses & curriculums changed so much in the past ~20 years that this isn't simply part of every introduction to the subject? Yes, the topic of code performance as a whole is more complex than just Big O, but as its own concept it was, in my time (get off my lawn!) pretty effective covered everywhere, and certainly the mom…
I think this might be for the self taught crowd of developers who never formally took Comp Sci, yet, who are also wielding important positions in software development that pay as well if not more than the guys who did take comp sci. You'd be astounded how big this self taught cohort could be and how much power they wield. They do their job pretty well, and yet, the basics of computer science is something that they ne…
Like the React team, claiming that they have found a revolutionary solution which is faster than direct DOM manipulation, where in reality it is perhaps only a constant factor faster. Nice in practice for small data, but not very interesting from a CS point of view.
Re: Big O Notation – Explained as easily as possible
#94If you are the kind of person that want to read an article titled "explained as easily as possible", I think you should just avoid saying the phrase "big oh" but instead talk about algorithm runtime more informally, like "quicksort has a worst case quadratic but average case n log n runtime". The risk is otherwise you will shoot yourself in the foot, maybe during an interview or other situation, as Big O is just one…
The problem with that is that informal use of big-o like notation is a lot more intuitive than the fancy language in your explanantion. Most people who can program can grasp the informal meaning of O(n^2) pretty easily. They may not connect the word quadratic to that say concept.
[deleted]
Re: Big O Notation – Explained as easily as possible
#95It's great to have a handle on big O but funny I've seen people index to it too much. An algorithm can look "really bad" from Big-O point of view and still be really good if: it's applied to a small enough input, or it's implemented very efficiently.
Most people jump to an extreme hyperbole instead of the reality what they're grappling with. Big-O is just that algorithmatised. Many software systems must be designed to anticipate orders of magnitude growth in scale.
However, I'm not sure about how most software systems grow -- not sure anyone really knows. We all have narratives about it, but it's a small, small subset of projects I know about that have an order of magnitude different number of users than when I first learned about them (other than moving to effectively 0).
Re: Big O Notation – Explained as easily as possible
#96If you are the kind of person that want to read an article titled "explained as easily as possible", I think you should just avoid saying the phrase "big oh" but instead talk about algorithm runtime more informally, like "quicksort has a worst case quadratic but average case n log n runtime". The risk is otherwise you will shoot yourself in the foot, maybe during an interview or other situation, as Big O is just one…
I know the rest of the notations in the family but, to be honest, even in most algorithmics textbooks they tend to use Big O like 90% of the time, even in contexts where Big Theta would be more precise (e.g. "mergesort is O(n log n) in all cases"). Let alone in more informal contexts.
I don't especially like it, but it's OK because it's not a lie. And I do think for people who just want the gist of the concept, like readers of this piece, it's enough and it's not worth being fussy about it.
What irks me is people who use the equal sign as in T(n)=O(n log n), though. Why would a function equal a class? Set membership notation does the job just fine.
Re: Big O Notation – Explained as easily as possible
#97Every one of these "Big-O explainers" says pretty much the same thing: count (or bound) the number of steps, then take the most significant term, and drop the constant associated with it. None of them explain why you take the most significant term or drop constant factors. I get why that is. You need the mathematical definition to demonstrate why that is, and most "Big-O explainers" don't want to assume any significa…
I'd say that the = is one of the most annoying abuses of notation that I know of, if not the most. Apart from not symmetric, which is a problem in its own right, for small o and small omega it's not even reflexive, which does not prevent the = users from using it also for those. Which amounts to using an equals sign to highlight how two functions differ.
And what do people gain with that? It's not as if a set membership symbol, which works just fine because big O, small o, the omegas and their ilk define sets of functions, doesn't work just fine and take the same space without being confusing.
Re: Big O Notation – Explained as easily as possible
#98It's great to have a handle on big O but funny I've seen people index to it too much. An algorithm can look "really bad" from Big-O point of view and still be really good if: it's applied to a small enough input, or it's implemented very efficiently.
Yes, it's good to remember that complexity analysis is only a theoretical topic that motivates certain approaches. When performance matters, you measure your program/system and use that as the ultimate guide for your work. Cache locality and branch prediction are two examples of practical issues that the theoretical approach will often ignore.
Re: Big O Notation – Explained as easily as possible
#99If you are the kind of person that want to read an article titled "explained as easily as possible", I think you should just avoid saying the phrase "big oh" but instead talk about algorithm runtime more informally, like "quicksort has a worst case quadratic but average case n log n runtime". The risk is otherwise you will shoot yourself in the foot, maybe during an interview or other situation, as Big O is just one…
I know the rest of the notations in the family but, to be honest, even in most algorithmics textbooks they tend to use Big O like 90% of the time, even in contexts where Big Theta would be more precise (e.g. "mergesort is O(n log n) in all cases"). Let alone in more informal contexts. I don't especially like it, but it's OK because it's not a lie. And I do think for people who just want the gist of the concept, like…
> even in contexts where Big Theta would be more precise (e.g. "mergesort is O(n log n) in all cases"
Just to be careful here: the difference between big/little oh/theta/omega is orthogonal to best/worst/average case.
A pedant could say that merge sort makes O(n^3) comparisons in both the best and worst case, ω(1) in both the best and worst case, etc. Colloquially, the former means "as fast as", and the latter means "slower than".
Re: Big O Notation – Explained as easily as possible
#100Earlier quoted context omitted.
The problem with that is that informal use of big-o like notation is a lot more intuitive than the fancy language in your explanantion. Most people who can program can grasp the informal meaning of O(n^2) pretty easily. They may not connect the word quadratic to that say concept.
Why wouldn't you be able to just say "worst case n^2?"
Dropping a constant