big o notation cheatsheet. when they say ___, they mean ____
O(1) - it takes the same amount of time, every time
O(log n) - you know binary search? that's happening somewhere
O(n) - there's a loop somewhere
O(n log n) - there's a loop, and in that loop is a binary search (or it's a binary search and each time it examines an item it's gotta do a loop)
O(n^2) - there's a loop in a loop, think iterating over the pixels of an n*n image
@blackle O(2^n) - E.g. Brute force on numbers, enumerating all subsets of something (the base doesn't matter, O(e^n) and O(123123^n) are treated the same)
O(n!) - Brute-force travelling salesman I guess?
@elomatreb O(n^n) - great gravy goodness what are you doing
O(n^n^n ... (n times) ... ^n^n) - please stop
@blackle O(n!) - this problem is above your pay grade. it's best you not try too hard.
@blackle ahhhhhhhhhh you rock :3
@blackle
O(n³) uh-oh, are we playing with voxels here?
O(2^n) aah not the graph traversal
O(n!) programmer, you've done fscked up
O(Rand()) what
O(💩) I quit *SIGSEGV*
@blackle This is wrong but I tend to think of it like this:
O(1) - fast but there's a catch
O(log n) - still fast
O(n) - not slow but it'll screw you over someday
O(n log n) - slow but someone worked hard to make it as fast as possible
O(n^2) - slow
this is also roughly ordered in terms of how "fast" something is, earlier in the list is "fastest"
"fast" is in quotes because the more items you have (larger the n) the more the O thing matters. so for small n, a constant time algorithm could get beaten by an n^2 time algorithm, but eventually if you have enough items the n^2 will take longer, bc the n keeps getting bigger but the O(1) stays the same