11 ms·
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) th
by brucedawson 6y ago
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).
- wtallis 6y agoThe 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.