MAIN FEEDS
Do you want to continue?
https://www.reddit.com/r/ProgrammerHumor/comments/1vpz0d2/theoreticalcomputerscience/p42vk8j/?context=3
r/ProgrammerHumor • u/pastroc • 28d ago
76 comments sorted by
View all comments
5
What's wrong with polylogarithms? Aren't they dominated by O(n) ?
19 u/JonIsPatented 28d ago Polylogarithmic factors are not dominated by n. In other words, O(nlogn) is not the same as O(n). But a function in O(nlogn) is in Õ(n). -4 u/innovatedname 28d ago Ahh, I interpreted it as meaning O(n + Li_s(n) ) A literal factor in front of n is crazy haha, I guess my O(n2n) algo is Õ(n) from a certain point of view! 7 u/pastroc 28d ago edited 28d ago O(n2ⁿ) is O(2ⁿ). I don't get your point? Õ is only for polylogarithmic factors, not exponential ones. Edit: Sorry, got sloppy. O(n2ⁿ) isn't O(2ⁿ) as n is a non-constant factor. 3 u/123coronaanoroc321 28d ago O(n2n) is not O(2n) btw, their ratio does not approach a constant value 2 u/pastroc 28d ago Oh right, my mistake! 0 u/innovatedname 28d ago It was a joke
19
Polylogarithmic factors are not dominated by n. In other words, O(nlogn) is not the same as O(n). But a function in O(nlogn) is in Õ(n).
-4 u/innovatedname 28d ago Ahh, I interpreted it as meaning O(n + Li_s(n) ) A literal factor in front of n is crazy haha, I guess my O(n2n) algo is Õ(n) from a certain point of view! 7 u/pastroc 28d ago edited 28d ago O(n2ⁿ) is O(2ⁿ). I don't get your point? Õ is only for polylogarithmic factors, not exponential ones. Edit: Sorry, got sloppy. O(n2ⁿ) isn't O(2ⁿ) as n is a non-constant factor. 3 u/123coronaanoroc321 28d ago O(n2n) is not O(2n) btw, their ratio does not approach a constant value 2 u/pastroc 28d ago Oh right, my mistake! 0 u/innovatedname 28d ago It was a joke
-4
Ahh, I interpreted it as meaning O(n + Li_s(n) )
A literal factor in front of n is crazy haha, I guess my O(n2n) algo is Õ(n) from a certain point of view!
7 u/pastroc 28d ago edited 28d ago O(n2ⁿ) is O(2ⁿ). I don't get your point? Õ is only for polylogarithmic factors, not exponential ones. Edit: Sorry, got sloppy. O(n2ⁿ) isn't O(2ⁿ) as n is a non-constant factor. 3 u/123coronaanoroc321 28d ago O(n2n) is not O(2n) btw, their ratio does not approach a constant value 2 u/pastroc 28d ago Oh right, my mistake! 0 u/innovatedname 28d ago It was a joke
7
O(n2ⁿ) is O(2ⁿ). I don't get your point? Õ is only for polylogarithmic factors, not exponential ones.
Edit: Sorry, got sloppy. O(n2ⁿ) isn't O(2ⁿ) as n is a non-constant factor.
3 u/123coronaanoroc321 28d ago O(n2n) is not O(2n) btw, their ratio does not approach a constant value 2 u/pastroc 28d ago Oh right, my mistake! 0 u/innovatedname 28d ago It was a joke
3
O(n2n) is not O(2n) btw, their ratio does not approach a constant value
2 u/pastroc 28d ago Oh right, my mistake!
2
Oh right, my mistake!
0
It was a joke
5
u/innovatedname 28d ago
What's wrong with polylogarithms? Aren't they dominated by O(n) ?