Question

The worst case complexity for following code segment is:

for(int i=1;i<=n;i++)
 {
  for(int j=1;j<=)
  {
     statement;
  }
 }

Options

• O(n+i)

• O(n×i)

• O(n)

• O(n²)

Answer 1

O(n²)

Explanation:

To find the complexity, we count how many times the "statement" inside the loops is executed:

Outer Loop: Runs from i = 1 to n

Inner Loop: For every value of i, the inner loop runs from j = 1 to i

Let’s look at the iterations:

• When i = 1, the inner loop runs 1 time.
• When i = 2, the inner loop runs 2 times.
• When i = 3, the inner loop runs 3 times.
• When i, = n the inner loop runs n times.

The total number of executions is the sum of the first n natural numbers.

Total Iterations = 1 + 2 + 3 + ... + n = `(n(n + 1))/2`

`(n^2 + n)/2`

= 0.5n² + 0.5n

In Big O notation, we keep only the highest-order term and ignore constants. Therefore, the worst-case complexity is O(n²).