3 ms·
I think the nicest way to learn this if you don't have a formal CS education is to still pick up a Discrete Math text book (like Chapter 3 in Rosen) and then re
by curiousDog 10y ago
I think the nicest way to learn this if you don't have a formal CS education is to still pick up a Discrete Math text book (like Chapter 3 in Rosen) and then read chapters 3 and 4 in CLRS.
- stcredzero 10y agoIf something puzzles you, don't be afraid to start drawing yourself a diagram. O(n^2) vs. O(n) amortized for naive string concatenation vs. growing a buffer by doubling: x xx xxx xxxx xxxxx xxxxxx xxxxxxx xxxxxxxx x xx xxxx xxxxxxxx This can be a good way of getting an intuitive feel for what's going on. Note in the 2nd case, you can stack all of 1st two rows representing cost into the 3rd row. In fact, you can always stack the execution costs into row (n-1) and never exceed the size of row n.
- curiousDog 10y agoLooks like you're alluding to the recurrence tree method for solving recurrences mentioned in CLRS. And you're right, it's a great way to visualize and get an intuitive feel of big-oh