In “Ace the Java coding interview”, section 1, problem set 3, in question 2, 1+2+3 +…+ n shouldn’t the BigO equals to n^2 instead of n?
Hi @Billy_Chau
Since we are counting the number of elements, n(n+1)/2 will return the sum of all numbers from 1 to n, so in that case, we are just running a loop n times.
If you still face any confusion, feel free to ask.
Happy learning,
This should be O(n^2).
For each position index, we are going to swap with all future indices ahead. That’s n(n-1)/2 which is O(n^2). You can’t finish generating all permutations in linear time to number of elements.