CODEWITHSUNDEEP
javaalgorithm
Learner
Learner

Reputation: 21393

time complexity of sorting inside while loop

I am trying to understand the time complexity of an algorithm with below pseudo code:

let nums has ArrayList of numbers

sort(nums)
while(nums.size() > 1) {
   // remove two elements
   nums.remove(0);
   nums.remove(0);

   nums.add(some_number);
   sort(nums);
}

sort(nums) is (N)Log(N). nums.remove(0) is O(N) nums.add() is O(1)

Now what is the time complexity for this algorithm.

Upvotes: 1

Views: 1430

Answers (1)

josejuan
josejuan

Reputation: 9566

The final complexity is O(n² log n) since you do n times the operation O(n log n).

Keep in mind that estimating complexity (O(...)) is not the same as establishing the total number of operations (usually the time function T(...) is given by total operations), they are two different concepts. A great introduction could be Analysis of Algorithms

Thus, the O(...) notation is a upper bound but T(...) is the real steps.

You can try to calculate exactly the T function, or you can go down the upper bound by improving O, but they will always be different functions, as O applies to the worst case of all possible entries.

In your code, we unknown T for the sort function, only their upper bound wich is O(n log n), then:

T(n) ≤ O(n log n) + T(3) + O((n - 1) log (n - 1)) + T(3) + O((n - 2) log (n - 2) + ...
T(n) ≤ O(n log n) + n T(3) + n O(n log n)
                               ^^^^^^^^^

Here, we cannot define exactly the T for sorting operations on n-1, n-2, ... that is the reason for establishing as a higher level O(n log n) for all of them. Then:

T(n) ≤ O(n log n) + n T(3) + n O(n log n)
T(n) ≤ O(n log n) + O(n) + O(n² log n)
T(n) ≤ O(n² log n)

In the second expression, we have a fixed number of upper bounds, in which case the upper bound will be the highest of the upper bounds.

(remove, remove and add is T(3), goto and comparisons are ignored)

Upvotes: 2

Related Questions