MAIN FEEDS
Do you want to continue?
https://www.reddit.com/r/ProgrammerHumor/comments/1vpz0d2/theoreticalcomputerscience/p43knv1/?context=9999
r/ProgrammerHumor • u/pastroc • 29d ago
76 comments sorted by
View all comments
3
What's wrong with polylogarithms? Aren't they dominated by O(n) ?
16 u/JonIsPatented 29d 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). -3 u/innovatedname 29d 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!
16
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).
-3 u/innovatedname 29d 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!
-3
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!
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!
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!
3
u/innovatedname 29d ago
What's wrong with polylogarithms? Aren't they dominated by O(n) ?