time complexity of sorting inside while loop

Question

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.

@WillemVanOnsem, I was able to understand complexity per line, but not able to understand what it will be when I add a while loop — Learner
– Learner, Commented Oct 6, 2019 at 16:14
hint, how will the size of the list change, after an iteration in the while loop? — willeM_ Van Onsem
– willeM_ Van Onsem, Commented Oct 6, 2019 at 16:20
@WillemVanOnsem, list decreases by 1 element, so while loop runs n times. So I think the overall complexity is (N^2)Log (N) . Is this correct? — Learner
– Learner, Commented Oct 6, 2019 at 16:22

josejuan · Accepted Answer · 2019-10-06 16:59:27Z

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)

Collectives™ on Stack Overflow

time complexity of sorting inside while loop

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related