[SOLVED] Worst and best case time complexity

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)

Leave a Reply

Your email address will not be published. Required fields are marked *