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 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.
- …