O(n^2), again, now in Windows Management Instrumentation • Hacker News Board

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

#191

Post by nitwit005 » Tue, Dec 10, 2019, 2:07 AM UTC

toast0 wrote: post #106

gameswithgo wrote: post #46

In the world of database backed web apps a related pattern is asking the database for some rows for a table, and then asking the database from some more rows, based on each row you just got. Rather than joining it together into one query. Makes it into production but falls down eventually!

I've actually had a lot of success going the other way. A database query with a join takes down production, so do a client side join, query one: get a bunch of ids from table A, query two: get a bunch of rows from table B, often as get one row from table B UNION get next row from table B etc. You can try using IN on the second query, but usually if that was going to work in a reasonable amount of time, your join woul…

I suspect you're just working around an issue with the query or the DB itself.

Previous company had to do something like that because of an Oracle perf bug way back (outer join issue I believe?), but they fixed it eventually and it was all deleted.

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

#192

Post by a1369209993 » Tue, Dec 10, 2019, 2:19 AM UTC

kortilla wrote: post #88

jtolmar wrote: post #59

Earlier quoted context omitted.

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.

What? It’s trivial to go exponential. for i in n: for j in n: whoops(i, j)

Actually, that should be:

  whoops(n):
    for i in n:
      whoops(n-1)

Your version is merely quadratic.

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

#193

Post by bentcorner » Tue, Dec 10, 2019, 2:34 AM UTC

leetcrew wrote: post #11

rcthompson wrote: post #3

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

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

You can always assert on insertion that n <= c. Or track the max size and assert on destruction.

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

#194

Post by samatman » Tue, Dec 10, 2019, 2:39 AM UTC

vecter wrote: post #159

chx wrote: post #147

Earlier quoted context omitted.

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

I propose Boltzmann sort: wait around until the heat death of the universe, and a Boltzmann brain will emerge from the cosmos, and sort your values while contemplating infinity.

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

#195

Post by School-Cotton » Tue, Dec 10, 2019, 2:49 AM UTC

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.

A good mnemonic is that a^b^c normally associates to the right because if you meant (a^b)^c, you could have just written a^(bc).

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

#196

Post by esoterica » Tue, Dec 10, 2019, 2:51 AM UTC

bsder wrote: post #125

stevefan1999 wrote: post #30

Earlier quoted context omitted.

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.

O notation is asymptotic by definition. The sentence “O(n) for small n” is completely meaningless. O(n) cannot never be different from O(2n) because they refer to the exact same set of algorithms.

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

#197

Post by xmprt » Tue, Dec 10, 2019, 3:05 AM UTC

thaumasiotes wrote: post #140

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.

> In general O(a^n) is strictly stronger than O(b^n) if a > b. Typo: O(a^n) is a stronger guarantee than O(b^n) if a b.

I took strictly stronger to mean a^n + b^n is O(a^n) so the a^n term holds more weight. The comment didn't mention anything about guarantees.

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

#198

Post by vortico » Tue, Dec 10, 2019, 3:15 AM UTC

concerned_user wrote: post #120

vortico wrote: post #117

Earlier quoted context omitted.

I definitely remember both reading about and experiencing this years ago, but I can't seem to find a source and it's driving me crazy (will search more later). I imagine variables would persist in the shell's memory. I'm talking about an implementation detail of the batch shell script parser/runner. I recall that some people would put GOTO statements to jump across large comment blocks in the days where reading a few…

It can be correct if you are talking about subprocesses/subshells of another batch script/command then yes, separate shell process will be spawned in each iteration.

No, I recall reading that the batch processor closes/re-opens the file, scans for n carriage returns where n is the current line number, executes that line, and repeats. These are the sources I found.

http://xset.tripod.com/tip3.htm "COMMAND.COM reads and executes batch files one line at a time; that means that it reads one line, execute it and rereads the file from the beginning to the next line." Perhaps this is a really old version of COMMAND.COM? Perhaps it's poorly stated but actually meant that it "rereads the file from the beginning of the next line to the next line".

https://docs.microsoft.com/en-us/windows/win32/fileio/local-... "Command processors read and execute a batch file one line at a time. For each line, the command processor opens the file, searches to the beginning of the line, reads as much as it needs, closes the file, then executes the line." This also seems to agree with my original claim.

I tested this with a batch script generated by

    print("@echo off")
    for i in range(1000):
        for j in range(1000):
            print("rem hello world")
        print(f"echo {i}")

and ran it using COMMAND.COM in a Windows 95's VM. It appears to run in linear time. Either COMMAND.COM was fixed, or both sources are incorrect.

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

#199

Post by mark-r » Tue, Dec 10, 2019, 3:24 AM UTC

lillecarl wrote: post #187

mark-r wrote: post #157

Earlier quoted context omitted.

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.

And here am I, just using what's in the standard library. of the language I'm writing. Never occured to me to try a different one.

This was quite a while ago, and the library sort was QSort which had a lot of overhead due to its calling convention. Today I'd have no problem using std::sort instead.

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

#200

Post by boneitis » Tue, Dec 10, 2019, 3:45 AM UTC

oneplane wrote: post #158

bananabreakfast wrote: post #127

Earlier quoted context omitted.

Yep, still wrong. Exponent != Exponential

I really should re-read some books. Thanks!

Don't fret it. Imo people are being unnecessarily curt when trying to flex their pedantry here, which we all love to do, myself included.

Of course, poly still means there is an exponential in the time complexity.

It's really nothing beyond the main takeaway that the usual norm to describe something as having "exponential" growth is that the number of computations increases in order of magnitude every time you add but a single item to the list of inputs.