5 ms·
>> The first graph demonstrates the O(n²) complexity of the algorithm. We can see that as the community grows larger, even by a small amount, the amount of iter
by anikan_vader 6y ago
>> The first graph demonstrates the O(n²) complexity of the algorithm. We can see that as the community grows larger, even by a small amount, the amount of iterations it takes to solve the matching problem grows exponentially.
This statement is contradictory. Probably the author is using "exponentially" to mean quick growth. I suppose this is alright in common parlance, but I find it disturbing when people describe a function as exponential just because it is a superlinear polynomial.
- pengaru 6y agoWhenever I visit family in the midwest this phenomenon makes me twitch. It seems people out there have taken to using "exponentially" as a pseudo-scientific word meaning "a lot". i.e. "you're making my job exponentially more difficult" Edit: fixed typo :)
- jacobush 6y agoThese phenomena make me twitch.
- ARandomerDude 6y agoIt seems like people out there are using "this phenomena" to mean "this phenomenon." I say this not to be rude, but to note that if we needlessly scrutinize each other's grammar, no one will be happy.
- wwarner 6y agoI'm smiling tho.
- beebmam 6y agoOn the other end of the spectrum, I like when people tell me "you're making my job exponentially more difficult, with a negative exponent" to let me know I'm doing a good job. Math nerds are the best coworkers
- sgillen 6y agoThis bothers me to no end too. But I’ve given up in every trying to fix it, it’s entered the public lexicon, if you want to talk about actual exponential growth you need to be more specific now.
- chasd00 6y agoi literally feel the same way about the current usage of the word "literally" and i mean that in the literal way. :)
- occamrazor 6y agoAnd the chart actually looks very close to linear
- e12e 6y agoEverything is linear on a log enough scale ;)
- whymauri 6y agoIt's not a log scale, though? It's just slightly unfortunate that the small curvature of the plot is hard to see.
- d4mi3n 6y agoGoing against the grain with this pun!
- Laakeri 6y agoNot exponentials
- greenshackle2 6y agoUh? log(2^x) == xlog(2) which is linear?
- tromp 6y agoif y = 2^x then taking logs of both x and y we have log y = 2 ^ log x, still an exponential relation. so it depends on whether "log enough scale" applies to both axes... Then there's functions like n -> 2^2^...^2 with an exponential tower of height n. That's doesn't become linear with any finite number of logs...
- timy2shoes 6y agoIf y = 2^x, then log y != 2^log x because of Jensen's inequality. You can take log of both sides to keep the equality, but applying the transformation inside of 2^() results in the equality turning into a strict inequality.
- zenhack 6y agoYeah, I'm willing to let this slide coming from regular folk in everyday conversations, but when you're writing a blog post about algorithms and you just said it was O(n^2)... this is a situation where I think it's reasonable to expect someone to hold to the technical meaning of a term.
- jointpdf 6y ago> ”I find it disturbing when people describe a function as exponential just because it is a superlinear polynomial.” This is the kind of statement people should put in their dating profiles if they want fewer but better matches. No, I’m not teasing you (ok just a little). Show quirky elements of yourself, just keep the mood sunny rather than salty.
- marknadal 6y agoI just say "beyond exponential" to get the idea across, despite that not actually grokking the hugeness of combinatorics.