91–100 of 232 posts
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)
Earlier quoted context omitted.
The one benefit of n^2 is it is really easy to do without any additional memory or data structure requirements. To make an n^2 algorithm n (or n log n), you pretty much always need to add in some constant time or logarithmic data structure. That requires tracking that structure, usually generating a good key, etc. I'm not saying that's really all that extreme. It just means your previous 5 line algorithm will often "…
That still makes no sense. The GP is literally just talking about switching from an association list to a hashmap : > Being written in a functional language meant that using association lists (linked lists for key/value) was very natural. […] After changing all the places to use a hash table it again ran in sub-second, although the code was nowhere near as elegant. You're not tracking more things (just tracking a has…
A trivial example, I recall about 1 month ago calling it out on a Javascript code review where someone was doing a `someList.find(x => x === "something")` inside a loop creating O(n^2) complexity. Rather than change the entire codebase wherever `someList` is used into a new type it is often easier just to suggest we build a Set (linear on length of `someList`) before the loop and use that for lookups within the loop (constant).
Of course, I am talking about circumstances clearly outside of your original model of OPs description. I am tracking more things (the new Set). However, I realize that to give the full context as to why the type of `someList` from my trivial example _couldn't_ be changed easily and why creating a new Set was the most prudent option would require a comment even longer than this essay. So I give OP the benefit of the doubt that he was in a similar situation where using the hashmap everywhere was either difficult or impossible.
Batch scripts themselves are O(n^2) because the shell closes and reopens them after each line (even comments or even blank lines), and the scan to get to line `n` takes O(n) time and disk bandwidth.
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)
See this stack overflow on polynomial vs. exponential: https://stackoverflow.com/questions/4317414/polynomial-time-...
https://stackoverflow.com/questions/12808934/what-is-p99-lat...
Earlier quoted context omitted.
> Eh, you're technically correct [...] The best kind of correct. Calling it O(n) then is the best way to express the performance improvement - I think that's the whole point of Big-O notation. However I agree that for smaller n one should not underestimate the constant factor impact.
The point was that you can often convert nested loops into two loops that are not nested. O(2n) conveys that, O(n) does not.
Excerpt: "I decided that the interactions were too complex to be worth analyzing in detail, especially without any thread names to give clues about what the 25 different threads in svchost.exe (3024) were doing." Future OS/Compiler Programming Note: It would be nice if threads could be individually named and those thread names shown/slowed/stopped/debugged in whatever tool implements Task Manager like functionality..…
That would help, but I think the root problem here (of the debugging difficulty, not the actual perf problem) is the Windows approach of having lots of unrelated services running together in a single process (svchost)
This reminds me I once wrote a hyper-exponential graph processing algorithm, in the range of O(2^2^n), and I still believe it was the right choice because: 1) It was much easier to understand than a faster alternative, and 2) I could mathematically guarantee that the largest value of n was something like 8 or 9, so you could argue that it was in fact a constant time operation.
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.
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,…
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.
Must be a typo. Since he was working with graph and I am assuming the problem is NP hard. Probably was of the order of 2^9