You must log in or register to comment.
Any algorithm can be O(n^2) if you only want it to be occasionally right.
Any algorithm can be O(1) if you cache all the answers beforehand.
isnt O(n³) usually simplified to O(n²) anyway ?
No, n³ cannot be O(n²) as otherwise that would mean that there exists a positive constant K and a positive threshold m such that for any integer n greater than m you would have n³ less than K*n², which would be the same as saying n less than K, which cannot hold for any integer n greater than m. So n³ cannot be an O(n²), which means that something that is an O(n³) is not necessarily an O(n²).
It’s the other way around, if something is an O(n²) then it is necessarily also an O(n³).
ok thanks
Impressive, very nice. Now let’s see LLM’s space complexity.