# 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**

2 min readJul 29, 2024

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 SortThis algorithm sorts the elements of an array.**

**Input: numb, an array of n integersOutput: 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.
- …