Hacker News Reader

Comment by goblin89 | Hacker News Reader

I want to develop a habit for looking at my code through the lens of time complexity.

What are some resources (articles, public knowledge bases, books, courses, etc.) that could make one more fluent in this matter? Something that could help build up time complexity intuition and learn to assess it faster.

View on HN

Watch for nested loops. That's pretty much it. Well that and be aware that if you have two nested loops then one of them had better be looping through log(n) the elements of the other or less.

The most common quadratic algorithms have two loops that both loop 'n' times, or the inner loop runs between 0 and n times. Both are quadratic - the second case is twice as fast, but still quadratic. In some cases the inner loop is not on 'n' at all but is on something that is typically proportional to 'n'. That's just as bad. That is, O(n*n/100) is still O(n^2).

The one exception to this is if you have nested loops not because you're going over your data multiple times, but simply because that's the most natural way to iterate over your data given how it's organized. If you have eg. a 2D array, then doubly-nested loops are usually the most straightforward way to iterate over the elements and aren't necessarily a red flag—many of the useful things you can do to a 2D array require touching each element at least once. But if you have triply-nested loops working on a 2D array rather than a 3D array, it's worth a second look.

Reply on news.ycombinator.com