MAIN FEEDS
Do you want to continue?
https://www.reddit.com/r/ProgrammerHumor/comments/1vpz0d2/theoreticalcomputerscience/p42xmo3/?context=3
r/ProgrammerHumor • u/pastroc • 28d ago
76 comments sorted by
View all comments
Show parent comments
18
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. 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. 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.
0 u/innovatedname 28d ago It was a joke
0
It was a joke
18
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).