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.