Big O Notation when first for loop is “for i = 1 to n” and secoond loop is “for j = 1 to n — i” is still O(n²) and WHY

Why is it still n²? Doesn’t the second loop greatly reduce the problem size?

Let’s use a pseudo code example to make things palpable.

Given this algorithm:

Simple Sort
This algorithm sorts the elements of an array.

Input: numb, an array of n integers
Output: numb, in ascending order

What is the asymptotic worst-case complexity?

The given algorithm is a form of Bubble Sort. To determine its asymptotic worst-case complexity, we need to analyze the number of operations performed in the worst-case scenario.

Analysis

Outer Loop (i loop):

• This loop runs from 1 to nnn.
• So, it executes nnn times.

Inner Loop (j loop):

• For each value of iii, this loop runs from 1 to n−in — in−i.
• For i=1i = 1i=1, the inner loop runs n−1n — 1n−1 times.
• For i=2i = 2i=2, the inner loop runs n−2n — 2n−2 times.
• …