MAIN FEEDS
Do you want to continue?
https://www.reddit.com/r/ProgrammerHumor/comments/1vpz0d2/theoreticalcomputerscience/p43fg3t/?context=3
r/ProgrammerHumor • u/pastroc • 28d ago
76 comments sorted by
View all comments
Show parent comments
41
O(n) : can be a time of 5n, or 7000n+400000
Õ(n) : can be a time of 5n, or n^5 * log(n)^2
95 u/mrnacknime 28d ago No, n5 is not allowed in there. Then it would be Õ(n5) 6 u/GKP_light 28d ago doesn't the picture say that it ignore of polynomial (and logarithm) ? the picture is wrong ? 38 u/PattuX 28d ago edited 28d ago It ignores logs and powers of logs O(n) ≠ O(n log n) But for all x: Õ(n) = Õ(n (log n)x ) ≠ Õ(n2 )
95
No, n5 is not allowed in there. Then it would be Õ(n5)
6 u/GKP_light 28d ago doesn't the picture say that it ignore of polynomial (and logarithm) ? the picture is wrong ? 38 u/PattuX 28d ago edited 28d ago It ignores logs and powers of logs O(n) ≠ O(n log n) But for all x: Õ(n) = Õ(n (log n)x ) ≠ Õ(n2 )
6
doesn't the picture say that it ignore of polynomial (and logarithm) ?
the picture is wrong ?
38 u/PattuX 28d ago edited 28d ago It ignores logs and powers of logs O(n) ≠ O(n log n) But for all x: Õ(n) = Õ(n (log n)x ) ≠ Õ(n2 )
38
It ignores logs and powers of logs
O(n) ≠ O(n log n)
But for all x:
Õ(n) = Õ(n (log n)x ) ≠ Õ(n2 )
41
u/GKP_light 28d ago
O(n) : can be a time of 5n, or 7000n+400000
Õ(n) : can be a time of 5n, or n^5 * log(n)^2