221–230 of 232 posts
Earlier quoted context omitted.
What? It’s trivial to go exponential. for i in n: for j in n: whoops(i, j)
That is polynomial time (specifically quadratic). See this stack overflow on polynomial vs. exponential: https://stackoverflow.com/questions/4317414/polynomial-time-...
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.
This is absolutely the better analysis. Many times, especially in agile-world, you get away with things as fast and as reasonable as you can. And that usually means O(n) as it is perfectly acceptable for a single call... But when an O(n) calls another O(n) is where you run into trouble. But at the beginning, nobody was planning for that call to be fast - implicit requirements lead it that way. In some ways, being abl…
Earlier quoted context omitted.
A little experience gets you that same red flag instinct in a hurry, too. [EDIT] it also makes you hesitate & second-guess and worry and experiment a bunch when contemplating using a recursive algorithm, which is deeply counterproductive in interviews where the expected behavior is so often "apply recursion, instantly and without hesitation" :-)
Unfortunately interviews seem to be all about dogma, and if you even mention performance you will get dinged for premature optimization. It’s like a postmodern religion where premature optimization is the cardinal sin, and you are supposed to burn as many cycles as possible to demonstrate that you are of good faith
Earlier quoted context omitted.
Actually, that should be: whoops(n): for i in n: whoops(n-1) Your version is merely quadratic.
I don't quite understand your code, but if I'm guessing correctly that n is an integer and "for i in n" means in human terms "for all non-negative integers less than n", that is not exponential, that is actually factorial, which is superexponential. Uh, or close to factorial, I'm not sure exactly. Testing it in python right now, incrementing a counter each time whoops is called, I'm seeing a relationship that looks l…
Fair point; I should have given:
whoops(n):
if(!n) return
for i in 2: whoops(n-1)
Earlier quoted context omitted.
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
Generally it is preferable to choose the pivot randomly.
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.
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.
Then my brain asked why you'd want to reduce a quadratic algorithm to exponential.
Earlier quoted context omitted.
It's actually pretty easy and there are package manifest in Arch that shows you how.
That’s just because someone went through that pain for you and scripted and packaged the entire procedure and rolled up most of the dependencies and their bills systems. I’ve done it from the official build directions without containers or prebuilt dependencies and “royal pain in the ass” is an understatement.
Earlier quoted context omitted.
That’s just because someone went through that pain for you and scripted and packaged the entire procedure and rolled up most of the dependencies and their bills systems. I’ve done it from the official build directions without containers or prebuilt dependencies and “royal pain in the ass” is an understatement.
Firefox is a nightmare to package that way.
Earlier quoted context omitted.
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
I always thought of Quadratic to be exponential but specifically 'N to the 2nd'. I suppose that does actually make no sense whatsoever. Thanks.