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

121–130 of 232 posts

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

#121

Post by z92 »

mehrdadn wrote: post #102
cogman10 wrote: post #101

Earlier quoted context omitted.

Depends. 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 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".

> where the keys looks something like "if (a > b and c Confused, what do you mean when you say the key is an "if" statement?

He probably meant, the lookup in the list is a conditional lookup based on a logic, instead of a simple key string.

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

#122

Post by oneplane »

gdxhyrd wrote: post #112
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,…

Quadratic, not exponential! :)

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.

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

#123

Post by vecter »

mathgladiator wrote: post #111
Google234 wrote: post #68

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.

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 evaluate it, I'm sure 999 or 1000 of them would evaluate it as 2^(2^9).

[0] https://en.wikipedia.org/wiki/Order_of_operations#Serial_exp...

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

#124

Post by ww520 »

vecter wrote: post #99
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,…

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.

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

#125

Post by bsder »

stevefan1999 wrote: post #30
savingGrace wrote: post #14

Earlier quoted context omitted.

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

you shouldn't call it O(2n), as there is already a constant inside of O(n), because it becomes 0 <= f(x) <= c*2n given a random f(x)

Asymptotically, that's true.

In reality, O(n) and O(2n) can be quite different for small n. As can O(n)+k0 and O(2n)+k1. Or worse, O(n^2)+k2 where sufficiently large k0 and k1 make the quadratic system better because it's k2 constant is so much smaller. Setup time matters.

Nowadays, you rarely have enough elements that the asymptotic behavior is the defining performance characteristic.

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

#126

Post by ww520 »

gdxhyrd wrote: post #112
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,…

Quadratic, not exponential! :)

Thanks for the correct term. The newsspeak of exaggerated figure of speech has got to me. :)

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

#127

Post by bananabreakfast »

oneplane wrote: post #122
gdxhyrd wrote: post #112

Earlier quoted context omitted.

Quadratic, not exponential! :)

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

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

#128

Post by blattimwind »

Craighead wrote: post #109
vecter wrote: post #99

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

What does exponential look like then?

2^n (by the virtue of Big-O, m^n is in O(2^n) for any fixed m).

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

#129

Post by w0utert »

oneplane wrote: post #122
gdxhyrd wrote: post #112

Earlier quoted context omitted.

Quadratic, not exponential! :)

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.

Quadratic complexity causes the runtime to grow quadratically ;-)

- Quadratic = x^2, e.g. 0,1,4,9,16,25,36,49,64,81

- Exponential = n^x, for example 2^x, e.g. 1,2,4,8,16,32,64,128,256

Already very bad for small x even if n=2, but for n higher than 2 you can imagine you will run out of time very, very quickly ;-P

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

#130

Post by mehrdadn »

z92 wrote: post #121
mehrdadn wrote: post #102

Earlier quoted context omitted.

> where the keys looks something like "if (a > b and c Confused, what do you mean when you say the key is an "if" statement?

He probably meant, the lookup in the list is a conditional lookup based on a logic, instead of a simple key string.

I'm confused what the variables are in this example—what's already in the container vs. what is being looked up. If we conceptually don't even have a proper mapping to begin with, then it doesn't make sense to ask whether it's hashable or comparable or not in the first place. If we do—then what is the "key" in this example?
Post reply on HN