O(n^2), again, now in Windows Management Instrumentation
randomascii.wordpress.com
O(n^2), again, now in Windows Management Instrumentation
1–10 of 232 posts
Re: O(n^2), again, now in Windows Management Instrumentation
#2A gem
> Dawson’s first law of computing: O(n^2) is the sweet spot of badly scaling algorithms: fast enough to make it into production, but slow enough to make things fall down once it gets there
Re: O(n^2), again, now in Windows Management Instrumentation
#3A gem > Dawson’s first law of computing: O(n^2) is the sweet spot of badly scaling algorithms: fast enough to make it into production, but slow enough to make things fall down once it gets there
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.
Re: O(n^2), again, now in Windows Management Instrumentation
#4A gem > Dawson’s first law of computing: O(n^2) is the sweet spot of badly scaling algorithms: fast enough to make it into production, but slow enough to make things fall down once it gets there
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.
This 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.
Re: O(n^2), again, now in Windows Management Instrumentation
#5A gem > Dawson’s first law of computing: O(n^2) is the sweet spot of badly scaling algorithms: fast enough to make it into production, but slow enough to make things fall down once it gets there
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.
Right, 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
Re: O(n^2), again, now in Windows Management Instrumentation
#6seems like building chrome is a loyal pain in the ass, so many bugs found in windows because of that :)
Re: O(n^2), again, now in Windows Management Instrumentation
#7Earlier quoted context omitted.
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.
This 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 abl…
Waterfall 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.
Re: O(n^2), again, now in Windows Management Instrumentation
#8Earlier quoted context omitted.
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.
This 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 abl…
> 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.
Re: O(n^2), again, now in Windows Management Instrumentation
#9Honestly, O(n^2) is probably okay for a diagnostic tool that's only meant to be run occasionally-- I'd like to know why Google's IT department felt the need to schedule it to run so frequently.
Re: O(n^2), again, now in Windows Management Instrumentation
#10Earlier quoted context omitted.
This 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 abl…
> 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…
That 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 (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.