Is the worst-case of this algorithm equal to $\Theta(n)$ or $\Theta(n\lg n)$? I am trying to find the worst-case complexity of the following algorithm. The input to the algorithm is a list of positive integers $a_1,\ldots,a_n$ and a bound $C$.


$S\gets$ empty set
$k\gets0$
for $i\gets1$ to $n$ do


add $i$ to $S$
$k\gets k+a_i$
if $k&gt;C$


$j\gets\arg\max_{i\in S}a_i$
$k\gets k - a_j$
remove $j$ from $S$




In the worst-case, at each iteration $i$, we go to the if condition and calculate the max. So, if the max operation requires $\Theta(n)$, then the worst-case complexity is $\Theta(n^2)$. As suggested in the comments, $\Theta(n)$ is not the best possible.

Here, I use an array to represent $S$. I can use a heap instead as a data structure to find the max in $\Theta(\lg n)$. So, the worst-case complexity is $\Theta(n\lg n)$. Am I right?

EDIT: I found this article https://cstheory.stackexchange.com/questions/18119/finding-smallest-k-elements-in-array-in-ok which finds the $k$ smallest elements in $O(k)$ time. My algorithm computes the $|S|$ smallest elements. Hence, it can be done in $O(|S|)$ time. But the $|S|$ is not given apriori. This is another issue now. Any help?
You need a data structure that supports the following three operations efficiently:


insert an element into the set
delete an element from the set
find the largest element in the set


There are multiple such data structures.  One reasonable choice is a balanced binary search tree, where all three operations can be implemented in $O(\log n)$ time.