CODEWITHSUNDEEP
algorithmtime-complexitybig-o
Self
Self

Reputation: 147

Big-O for While loop

I have this algorithm, and I am trying to calculate its complexity.

A = {a_1, a_2, a_3, ...}
w = 0
while A != empty
   a' = argmin(A)  #a' is the element with smallest y_a
   if (N_a' + w > C)
      A = A - {a'}
   else
      x_a' = x_a' + 1
      w = w + N_a'
      Update the y_a' value in A using x_a'

A is a set, and if the condition (N_a' + w > C) is true, we remove an element from the set until the set is empty. I know that the algorithm runs at least O(n), but it can run more if the if statement is false. Assume the last line (the update) takes a constant time.

How can I calculate the complexity here?

Upvotes: 0

Views: 1946

Answers (1)

Henry
Henry

Reputation: 43728

Let's first determine how often the then and else branches can run in the worst case. In the then branch the set A becomes smaller by one element so it can only be executed n times (where n is the initial number of elements in A). The else branch can be executed at most C times (take N_a' = 1, it must be >= 1). C is a constant so this is O(1). The total number of iterations is therefore O(n).

The critical point is now the data structure used for A. Three operations have to be supported: finding the min, removing the minimum element, and the update in the last line. When we choose a min-heap, each of these operations can be done in O(log n). Note that the update is not O(1) time in this case. The total run time is now O(n log n).

A naive minimum search (i.e. using an uordered array for A) makes the operations min, remove element, and update O(n), O(1), and O(1) respectively. The total run time would therefore be O(n*n).

Using an ordered array to represent A we get run times of O(1), O(1), and O(n) respectively for our three operations. The min search O(1) operation is executed for each iteration, so O(n) times. The remove elemnt O(1) operation is in the then branch, so executed O(n) times, the update O(n) operation is in the else branch, so executed O(1) times. Taking all together gives a runtime of O(n). However, if the set has to be sorted in the beginning we are again at O(n log n).

Upvotes: 1

Related Questions