| ▲ | onionisafruit an hour ago |
| For those of us uninformed, what’s the difference between O and o? |
|
| ▲ | bobmarleybiceps an hour ago | parent | next [-] |
| Knuth originally defining them https://dl.acm.org/doi/10.1145/1008328.1008329 |
|
| ▲ | ruined an hour ago | parent | prev | next [-] |
| f(n) = O(g(n)) means as n increases, f(n)/g(n) must not grow beyond a constant f(n) = o(g(n)) means as n increases, f(n)/g(n) must shrink |
| |
| ▲ | jhanschoo 44 minutes ago | parent [-] | | Nitpick: s/must shrink/must eventually shrink, after finitely many n/ Equivalently, must go to zero in the limit. | | |
| ▲ | Davidzheng 11 minutes ago | parent [-] | | depends on what you think shrink means. If you mean decreasing, that's false even eventually. |
|
|
|
| ▲ | theokrueger an hour ago | parent | prev | next [-] |
| Big O basically drops constants O(2n+1) = O(2n) = O(n) o(2n+1) > o(2n) > o(n) Both define upper boundary, but big O can read like "the function is generally proportional to ___" and little o can read like "the function is never more than _____" |
| |
| ▲ | bobmarleybiceps an hour ago | parent [-] | | that's not the convention I know... (from CLRS algorithms book). Big O is sort of like <=.
little o is sort of like <. https://dl.acm.org/doi/10.1145/1008328.1008329 | | |
| ▲ | npinsker an hour ago | parent [-] | | yes, GP is slightly off, but the idea of <= and < is accurate. O(n) is: "there exists a K such that, for sufficiently large n, K*n is always larger". o(n) is: "for every K, for sufficiently large n, K*n is always larger". (So o(2n+1) and o(2n) and o(n) are the same thing.) |
|
|
|
| ▲ | boothby an hour ago | parent | prev | next [-] |
| If f is O(g) and o(h) then Lim f/g -> C a constant
And Lim f/h -> 0
|
| |
| ▲ | adgjlsfhk1 43 minutes ago | parent | next [-] | | > Lim f/g -> C a constant. This isn't quite correct. O(g) doesn't require the limit to exist. | |
| ▲ | appplication an hour ago | parent | prev [-] | | Lmao! If someone is asking the difference between big and little o notation this is absolutely not the right way to clarify it. If you were joking then maybe you got me | | |
| ▲ | boothby an hour ago | parent [-] | | I do hope you can find and reattach your ass; that does sound painful. |
|
|
|
| ▲ | Ygg2 an hour ago | parent | prev [-] |
| Both are upper bounds. But small o is strictly smaller than upper bound. Big O is not greater than upper bound. https://stackoverflow.com/questions/1364444/difference-betwe... |
