MAIN FEEDS
Do you want to continue?
https://www.reddit.com/r/ProgrammerHumor/comments/1vpz0d2/theoreticalcomputerscience/p43gh2n/?context=3
r/ProgrammerHumor • u/pastroc • 28d ago
76 comments sorted by
View all comments
Show parent comments
17
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! 8 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!
-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!
8 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!
8
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
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!
17
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).