## Issue

I need help understanding the worst and best case time complexity for the following code example. How can I represent the time as a function T(n) if each line of code takes X time?

Thank you.

```
SORT(X)
for i = 0 to X.length - 1
for j = X.length downto i + 1
if X[j] < X[j-1]
change X[j] with X[j-1]
```

## Solution

As stated in the comments, best case occurs when for all `j`

, `X[j] >= X[j - 1]`

, that is, your list `X`

is already sorted in ascending order. Worst case occurs when for all `j`

, `X[j] < X[j - 1]`

, that is, your list `X`

is already sorted in descending order. However notice that regardless of the situation, we have to iterate through the loops and execute the if statement. Only difference is the swapping operations, which won’t effect the time complexity analysis.

For all `i`

, we iterate from `X.length`

to `i+1`

.

For `i`

= 0, iterate from `X.length`

downto `1`

: `n`

operations (assuming `X`

has `n`

elements.)

For `i`

= 1, iterate from `X.length`

downto `2`

: `n-1`

operations

For `i`

= 2, iterate from `X.length`

downto `2`

: `n-2`

operations

…

For `i`

= `X.length`

– 1, iterate from `X.length`

downto `X.length`

: `1`

operations

Sum the number of operations: `n`

+ `n-1`

+ … + `1`

= (`n+1`

) . (`n`

) / 2

Therefore we can conclude that `T(n) = n*(n+1)/2`

. Time complexity for both of the cases (worst-best) becomes: `O(n^2)`

.

Answered By – Muhteva

Answer Checked By – Katrina (BugsFixing Volunteer)