2
$\begingroup$

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>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?

$\endgroup$
  • 3
    $\begingroup$ Have you noticed that computing the max in each iteration is re-doing a lot of work over and over again? Can you think of any faster way to update the max, without having to redo all that work? Perhaps some appropriate data structure might be helpful here. What data structures have you considered, for storing $S$? $\endgroup$ – D.W. Apr 11 '18 at 21:41
  • $\begingroup$ Do you mean "set"? A set by definition doesn't contain duplicates, so if for example n = 1000, C = 100 and a1..a1000 = 1, the result would be one element { 1 }. Maybe you mean an unordered list? $\endgroup$ – gnasher729 Apr 11 '18 at 22:00
  • $\begingroup$ Theta (n log n) is easy if you know what data structures to use. Theta (n) - I wouldn't say it's impossible. The result is the m smallest items for some unknown m. Slightly more difficult than finding a percentile which can be done in linear time (because you don't know which percentile you want when you start). $\endgroup$ – gnasher729 Apr 11 '18 at 22:06
  • $\begingroup$ $S$ is a set. If $a_1=a_2=\ldots=a_{1000}=1$, and $C=100$, I would add $1$ to $S$, then $2$ to $S$, etc. So, I would get $S=\{1,2,\ldots,100\}$. I only add to $S$ distinct elements. You are right about sorting but what if I use a list that stores the max values encountered so far. Whenever I update $S$, I update this list. So in every iteration of the for loop, I can calculate the maximum in $O(1)$ time. Like this, I can achieve $\Theta(n)$, Is this right? $\endgroup$ – kik Apr 12 '18 at 0:06
  • $\begingroup$ @D.W. I considered a set for $S$, is it enough to calculate the max in $O(1)$? $\endgroup$ – kik Apr 12 '18 at 12:27
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.