What is complexity of this code snippet?

Technology CommunityCategory: Big-O NotationWhat is complexity of this code snippet?
VietMX Staff asked 3 years ago
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.