8 ms·
I think the other reason O(n^2) is a "sweet spot" is that it often arises from one O(n) algorithm calling another O(n) algorithm in each iteration, resulting in
by rcthompson 7y ago
I think the other reason O(n^2) is a "sweet spot" is that it often arises from one O(n) algorithm calling another O(n) algorithm in each iteration, resulting in O(n^2) overall. Very often it's ultimately because the inner O(n) algorithm should have been implemented as O(1), but nobody bothered because it was never intended to be called in a loop.
- cross_wiber 7y agoThat's a good point. It explains why you can very often unintentionally end up with an O(n^2) algorithm in the first place, and Dawson's law then explains why no one bothers to fix it until it's too late.
- brucedawson 7y agoHey, it's Dawson's first law of computing. I have more planned, and it's important to distinguish them.
- crankylinuxuser 7y agoThis is absolutely the better analysis. Many times, especially in agile-world, you get away with things as fast and as reasonable as you can. And that usually means O(n) as it is perfectly acceptable for a single call... But when an O(n) calls another O(n) is where you run into trouble. But at the beginning, nobody was planning for that call to be fast - implicit requirements lead it that way. In some ways, being able to identify and detect resource usage is what is nice about waterfall. Identification of critical API calls and respective timings would be integral to continue building the GUI elements. But we all know how waterfall is poo-pooed these days.
- ComputerGuru 7y ago> Many times, especially in agile-world, you get away with things as fast and as reasonable as you can. Which has led to the ridiculous software bloat we have today. This always MVP, break fast, break often garbage needs to die.
- chousuke 7y agoI feel like the concept of an MVP is often abused. It shouldn't be a thing that somehow works with bubblegum and luck; it should still be "solid". The point ought to be to leave out features, not quality.
- NateEag 7y agoWhen you leave out features and quality, you have a proof of concept. Those are valuable things to build, IMO. Just make sure you leave out enough features that it cannot be pushed into production once someone else sees it running.
- TimTheTinker 7y agoWaterfall refers more to the fact that further work (development, testing, or deployment) has to wait for someone else to finish something else first. Multiply that by how many “steps” something has to go through before being released. This implies everyone is taking work in large chunks instead of small iterations, and that too much is being planned too early instead of learning as you go. Taking things iteratively, small iterations, delaying decisions, learning as you go — that’s what agile development is. And all the stuff you mention above is possible when developing with agility.
- pjc50 7y ago> Identification of critical API calls and respective timings would be integral to continue building the GUI elements. But we all know how waterfall is poo-pooed these days. If you've worked out which API calls are happening and how often, you've already written most of the application. It's just that it might be on paper or in pseudocode. Waterfall was abandoned because getting to that level of detail takes far too long for management to accept and it's easier - sometimes orders of magnitude faster - to write the thing as actual code, try it, and then see what needs improving. And see what was wrong with the requirements.
- retrovm 7y agoThat presupposes that you can start with a big pile of bad APIs and somehow incrementally approach something worth having. That's not consistent with my experience. In my experience the innermost APIs, the ones that get written down first, are effectively cast in stone and dictate the quality of the whole product, forever. The first draft of a system is the one that should have all its APIs worked out with a pencil before any code is written. You get these accidental complexity explosions precisely because someone thought it was easy and obvious to write a function returning std::vector<string> (or whatever) and didn't consider from the caller's point of view that making the function take an output iterator might be less complex.
- jacobolus 7y agoYou are right. It is typically more effective to write one implementation as a hacky prototype, play with it a bit, throw it away, and then rewrite a production implementation from scratch, so that the mistakes of a design made by someone inexperienced don’t get baked in forever. Unfortunately there are cultural/psychological factors which often preclude or discourage this method, even if it would save time and produce better code in the medium term than either exhaustive planning up front uninformed by practice OR just iterating the initial broken version to continually meet new requirements.
- BlueTemplar 7y agoLol, ninjaed, see above.
- justincredible 7y agoWaterfall the UI/UX, Agile the functionality.
- ludamad 7y agoRight, if we consider O(n) "ideal" (for many domains, this is true), we can consider processing per item as a more convenient metric. If you go above, say, O(log n) processing per item, you're in trouble proportionate to the unintended success of this portion of the code. Very easy to write a sloppy utility with a nice API, only for it to be 'the perfect fit' for someone else's tight deadline, become an idiom in the code, finally see a 10,000 entry example much later
- leetcrew 7y agosometimes it was correct to choose O(n) instead of O(1). if you know you're only going to have very few elements, linear search on a vector can be faster than a hashtable lookup or rb-tree traversal and use less memory for the data structure. later on some clown decides to expose your private function for their own convenience and starts calling it with thousands of elements.
- mrec 7y agoYou're not wrong, but IMHO the proper place for that sort of optimization is inside the dictionary class/module/whatever. It knows why the optimization is there and the conditions under which it makes sense. For application code it's probably better to express clearly what you're trying to do, in this case keyed lookup. Throwing in a linear search at that level isn't just dangerous, it's potentially confusing to people reading the code later.
- cogman10 7y agoDepends. Sometimes the key isn't easily hash or comparable. For example, I know of a few case where the keys looks something like "if (a > b and c < d) or (a < b and d == b)". Now, that doesn't mean you can't hash a, b, c, and d. It just means that the logic around doing the lookups is nontrivial. When you are talking about < 100 elements, sometimes the consideration is "Welp, this is < 100, so lets just n^2 it".
- savingGrace 7y agoI often see O(n^2) algorithms that can be reduced to O(2n) at the very least. One of the best things I gained from school was the red flag that fires off in my mind any time I see a loop nested in a loop.
- TravHatesMe 7y agoO(2n) = O(n)
- shantly 7y agoA little experience gets you that same red flag instinct in a hurry, too. [EDIT] it also makes you hesitate & second-guess and worry and experiment a bunch when contemplating using a recursive algorithm, which is deeply counterproductive in interviews where the expected behavior is so often "apply recursion, instantly and without hesitation" :-)
- deleted 7y ago[deleted]
- nikanj 7y agoUnfortunately interviews seem to be all about dogma, and if you even mention performance you will get dinged for premature optimization. It’s like a postmodern religion where premature optimization is the cardinal sin, and you are supposed to burn as many cycles as possible to demonstrate that you are of good faith
- WorldMaker 7y agoOn the flipside, I've met different sorts of interviewers that ding someone for writing something intentionally unoptimized in the spirit of avoiding premature optimization for algorithmic clarity, because don't they have rote knowledge that "x is faster". Dogma on every side of the fence. (Also, continuing proof that technical interviews will never be objective evaluations of skill.)
- stevefan1999 7y ago
- Tade0 7y agoOr those two should have been combined into O(nlogn) via sorting.
- 52-6F-62 7y agoOr if you've already made allowances for the memory usage, you can also check to see if you can write your O(n^2) nested loops as O(n) + O(n) depending on the shape of your data.
- masklinn 7y ago> it often arises from one O(n) algorithm calling another O(n) algorithm in each iteration, resulting in O(n^2) overall. https://accidentallyquadratic.tumblr.com https://accidentallyquadratic.tumblr.com was / is pretty much an entire blog dedicated to this.
- jtolmar 7y agoProgramming languages have native support for O(n) algorithms in the form of for loops. You can compose as many of those as you want to get a huge polynomial, but you have to go out of your way and do something a bit weird to get an exponential run time.
- kortilla 7y agoWhat? It’s trivial to go exponential. for i in n: for j in n: whoops(i, j)
- esotericn 7y agoThat's n^2.
- reggieband 7y agoThat is polynomial time (specifically quadratic). See this stack overflow on polynomial vs. exponential: https://stackoverflow.com/questions/4317414/polynomial-time-and-exponential-time https://stackoverflow.com/questions/4317414/polynomial-time-...
- justincredible 7y agowhoops is O(2^n)
- _wldu 7y agoTwo for loops, one nested under the other, both upto N is clearly O(N^2) in the worst case. Three for loops (in the same manner) is O(N^3).
- a1369209993 7y agoActually, that should be: whoops(n): for i in n: whoops(n-1) Your version is merely quadratic.
- trehalose 7y ago
- lmm 7y agoI don't think that's a real insight. You could equally say that O(n^3) should be a sweet spot because you can nest a loop 3 deep, and so on for n^4, n^5 and so on. But we don't see these cases making it out into the wild because they're caught in testing.
- wesammikhail 7y agoA useful heuristic from my CS professor: always treat every tab (indentation / complexity) to be equivalent to a cart that you are attaching your horse. Add enough carts (complexity) and you will soon be asking yourself why your horse isnt a nuclear reactor instead?