Earlier quoted context omitted.
2^2^9 is 1.340781e+154
In this format, exponents are evaluated left to right, so this is 4^9 which is 262144 and is reasonable.
But that would not be hyperexponential as GP claimed.
O(n^2), again, now in Windows Management Instrumentation
151–160 of 232 posts
Re: O(n^2), again, now in Windows Management Instrumentation
#152Earlier 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.
Programming 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.
Recursion is a pretty good way to exponential quickly.
Re: O(n^2), again, now in Windows Management Instrumentation
#153Earlier quoted context omitted.
'winmgmt.exe /verifyrepository', the tool with the O(n^2) behavior, is a diagnostic tool-- it verifies the consistency of the WMI repository.
He used that to manually reproduce, but the original behaviour wasn't caused by manually calling the winmgmt executable with the /verifyrepository switch. Instead the repo was being verified as a side effect of another WMI operation.
I believe that the repo gets verified automatically as a daily thing, but our IT department was verifying it hourly. They have stopped.
I think that the hourly verification was put in to try to diagnose some problems that were actually or suspected to be related to WMI corruption.
Even daily verification is going to cause problems, they are just less likely to be noticed, until they get to the 30+ minutes level.
Re: O(n^2), again, now in Windows Management Instrumentation
#154Honestly, 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.
It's sort of unclear why 3 billion bytes needs to be processed in an O(N^2) algorithm in the first place, but seems especially egregious in that it also blocks other processes from running. One other aspect of the issue is that it's unclear why that database is now so large. It seemed like different machines had different sized databases — perhaps one angle of the solution is trimming and vacuuming.
Well, it doesn't block all other processes, but it sure did block a lot of them.
I agree that finding out why the repository is huge seems worthwhile. I think it's been growing lately which means it might eventually get to an unsustainable size. As far as I can tell Microsoft doesn't ship any tools to make repo-size analysis easy. An open-source tool was suggested in one of the comments on my blog.
Re: O(n^2), again, now in Windows Management Instrumentation
#155Earlier quoted context omitted.
n^2 is polynomial, not exponential. If it was truly exponential (which a sort should never be unless you've decided to solve an arbitrary 3-SAT problem while sorting a list), then it would've blown up in your face much sooner.
You're correct n^2 is polynomial, not exponential. It was just an exaggerated figure of speech. BTW, O(n) and O(n log n) are also polynomial; it just doesn't have the punch to it.
So the more precise term would be quadratic.
"Exponential" is indeed misused.
Half the time I hear it, it is lower, like quadratic or cubic. The other half the time is higher, like combinatorial.
Re: O(n^2), again, now in Windows Management Instrumentation
#156Well, now this show how polynomial time isn't necessarily any better than O(2^n), or exponential time in reality. Once the k grew bigger in O(n^k), our modern machine will still struggle to run it.
O(N^2) is strictly better than O(2^N). Per the article, this algorithm fell over at 3 billion bytes of data, but wasn't especially noticeable at 300 million bytes of data.
Better from an theoretical perspective. Depending on n and any constant factors, one or the other may end up winning in reality.
Re: O(n^2), again, now in Windows Management Instrumentation
#157Earlier quoted context omitted.
I once coded a bubble sort in an application where I expected the worst case to be n=4. Later that assumption was invalidated, but I had long ago moved on to something else. I hope the person who inherited my code doesn't still hate me.
Why bubble sort? I never understood its popularity. Selection sort feels a lot more intuitive to me and it's the same complexity.
Bubble sort is the first one I learned, so I remember it the best. I never spent any time comparing any of the O(n^2) sorts so it never occurred to me to try a different one.
Re: O(n^2), again, now in Windows Management Instrumentation
#158Earlier quoted context omitted.
Would it be correct to say it's a quadratic complexity causing the run time to grow exponentially? Or is the word exponential still wrong here. My Mathematics terminology is rather.. dusty.
Yep, still wrong. Exponent != Exponential
I really should re-read some books. Thanks!
Re: O(n^2), again, now in Windows Management Instrumentation
#159Earlier quoted context omitted.
n^2 is polynomial, not exponential. If it was truly exponential (which a sort should never be unless you've decided to solve an arbitrary 3-SAT problem while sorting a list), then it would've blown up in your face much sooner.
> which a sort should never be There's certainly a most awesome sort algorithm which is exponential... https://www.dangermouse.net/esoteric/bogobogosort.html They are not even sure what the complexity is but it's like O(n!^(n-k)) or O(n*(n!)^n).
I'm aware of bogosort and its crazy variants, but let's not be ridiculous here. You could make any "sorting" algorithm arbitrarily bad if you'd like by doing such silly but useless things.
Re: O(n^2), again, now in Windows Management Instrumentation
#160Earlier quoted context omitted.
In this format, exponents are evaluated left to right, so this is 4^9 which is 262144 and is reasonable.
That's certainly not the standard. If anything, exponentiation is usually performed right to left, with some exceptions [0]. However, the fact that we even have carets in this conversation isn't because the GP wanted to adopt a left-to-right convention, but due to limitations in the richness of HN's text editor. If you write a tower of 2^2^9 on a whiteboard and ask 1000 mathematicians and computer scientists to evalu…
I'm a mathematician and a computer scientist, so I must be one in a thousand. The link even indicates that ambiguity exists in wild, and I think clear notation would help.
In this case, the absurdity of the number suggests a more realistic number.