CODEWITHSUNDEEP
algorithmperformancetime-complexity
ThreeTherteen
ThreeTherteen

Reputation: 3

Worst and best case time complexity

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]

Upvotes: 0

Views: 679

Answers (1)

Muhteva
Muhteva

Reputation: 2832

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

Upvotes: 1

Related Questions