Problem
Consider this code:
for(int i = 0; i < n; i++){
for(int j = i; j < n; j++){
array[j] += 2;
}
}
What is complexity of this code snippet?
This is O(n2)
(or Quadratic complexity) since for each pass of the outer loop (O(n)
) we have to go through the entire list again so the n’s multiply leaving us with n
squared.