Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

O(n^2), again, now in Windows Management Instrumentation

randomascii.wordpress.com

Post reply on HN
Print view View original

171–180 of 232 posts

Re: O(n^2), again, now in Windows Management Instrumentation

#171

Post by brucedawson »

jgalar wrote: post #133
albertzeyer wrote: post #22

Earlier quoted context omitted.

For reference, this was the old API: https://docs.microsoft.com/en-us/visualstudio/debugger/how-t... This was well known, and many applications actually used that. Of course it was very ugly. I don't think it would have been a problem to also rename a given thread multiple times, but not sure.

It's very ugly, but at least it doesn't seem to limit you to 15 characters like on Linux (prctl/pthread_set_name_np). That limit makes it pretty hard to provide meaningful identifiers in a non-trivial application.

Funny thing, windbg apparently uses a fixed-size buffer to store the old-style thread names and it must use strncpy to copy them in because if your thread names are long enough then windbg displays the first ~15 characters and then shows garbage, because strncpy doesn't guarantee null-termination.

Harmless I think, but sloppy.

Re: O(n^2), again, now in Windows Management Instrumentation

#172

Post by enedil »

thaumasiotes wrote: post #143
BlackFingolfin wrote: post #96

Earlier quoted context omitted.

Actually O(2n) did not convey this for me at all, all it did for me was cause confusion. If this ("turn it into two not nested loops") was indeed intended, I'd suggest to spell it out, not abuse notation

> If this ("turn it into two not nested loops") was indeed intended, I'd suggest to spell it out, not abuse notation O(2n) is not an abuse of notation. It's just as well defined as O(n). The fact that O(2n) is a subset of O(n) is a theorem, not part of the definition of the notation.

It's a subset, but also a superset.

Re: O(n^2), again, now in Windows Management Instrumentation

#173

Post by emn13 »

paulddraper wrote: post #155
ww520 wrote: post #124

Earlier quoted context omitted.

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.

Combinatorial? Seriously? The difference between exponential and cominatorial is essentially purely theoretical when it comes to computational complexity. In practice, even the difference between n and n log n is barely relevant, and the exponential and combinatorial are the exponentiation thereof. Nobody ever, ever deals with processes large enough where the difference both matters, and the process completes. Even a tiny scaling factor in the exponent and a moderate base means the point at which a unscaled combinatorial passes it will take more steps that you might as well be waiting for the heat death of the universe.

But even without any scaling factors, don't underestimate the size of the numbers involved. If you had two threads, one simply counting up to some n! upper bound, and the other up to 10^n - how long do you think the minimum problem size would take for the "slow" combinatorial to actually be slower than the exponentiation? Hint: at 4GHz and 1 op/cycle... Let's just say I'm not holding my breath that our species will still be around then. And even a tiny scaling factor to the mix...

I mean, if you're trying to estimate computational complexity at least, this nuance seems pointless.

But quadratic vs. exponential really matters, with plausible parameters.

Re: O(n^2), again, now in Windows Management Instrumentation

#175

Post by thaumasiotes »

enedil wrote: post #172
thaumasiotes wrote: post #143

Earlier quoted context omitted.

> If this ("turn it into two not nested loops") was indeed intended, I'd suggest to spell it out, not abuse notation O(2n) is not an abuse of notation. It's just as well defined as O(n). The fact that O(2n) is a subset of O(n) is a theorem, not part of the definition of the notation.

It's a subset, but also a superset.

Yes? But to replace O(2n) with O(n), you only need that it's a subset.

Re: O(n^2), again, now in Windows Management Instrumentation

#176

Post by np_tedious »

blattimwind wrote: post #169
aliceryhl wrote: post #136

Earlier quoted context omitted.

This is untrue: There's no constant k such that k*2^n > 3^n for all n. In general O(a^n) is strictly stronger than O(b^n) if a > b. This is why you sometimes see complexities that are e.g. O(1.3894732894^n) in wikipedia articles on the best known cases for various algorithms.

Thanks for the correction.

Sounds like perhaps you confused with the other direction: that the base of log(n) doesn't matter

Re: O(n^2), again, now in Windows Management Instrumentation

#177

Post by vecter »

mathgladiator wrote: post #160
vecter wrote: post #123

Earlier quoted context omitted.

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.

Don't you think it's more likely that the original poster made a mistake and that a graph algorithm isn't actually O(2^2^n)? I can't name a single meaningful algorithm that has that time complexity.

Re: O(n^2), again, now in Windows Management Instrumentation

#178

Post by vecter »

mathgladiator wrote: post #113
vecter wrote: post #75

Earlier quoted context omitted.

Could you explain more? As the other commenter pointed out, 2^2^9 = 2^512 which is an astronomically large number (far more than the number of atoms of ordinary matter in the observable universe). Something doesn't seem right.

Why couldn't it be (2^2)^9 = 4^9 = 262144 ?

Why wouldn't he just write O(4^n) then? That'd be like saying "I counted the cats in the room and there were 2+2 cats".

Re: O(n^2), again, now in Windows Management Instrumentation

#179

Post by lmm »

rcthompson wrote: post #3
harikb wrote: post #2

A 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.

I 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.

Re: O(n^2), again, now in Windows Management Instrumentation

#180

Post by hhmc »

ww520 wrote: post #79

Ah, this brings back the memory of my O(n^2) fiasco. I wrote a low level file system storage driver in the past. In the caching layer, there's a need to sort by LRU time for cache eviction. It's a minor thing not run often and I wanted to move quickly. Also since it's low level kernel mode code, I wanted the code to be simple and correct. The number of cache entries was not big. Bubble sort was adequate for small N,…

Quick sort can be made to be O(n log n) with careful choice of pivot - e.g. https://en.wikipedia.org/wiki/Median_of_medians
Post reply on HN