3 ms·
Isn’t a loop k from 1 to n, with an inner loop k to n, actually order n! (The article says O n^2) ?
by efitz 8y ago
Isn’t a loop k from 1 to n, with an inner loop k to n, actually order n! (The article says O n^2) ?
- ishitatsuyuki 8y agoAdding up 1+2+...+n equals to n(n-1)/2, which when converted to an order becomes O(n^2).
- joppy 8y agoAn outer loop [1, n] and inner loop [k, n] is cheaper than an outer loop [1, n] and inner loop [1, n], and this second pair of loops runs in O(n^2) time.