0
$\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?

Improve this question
$\endgroup$
12
  • 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. ♦
    Commented Apr 11, 2018 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
    Commented Apr 11, 2018 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
    Commented Apr 11, 2018 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
    Commented Apr 12, 2018 at 0:06
  • $\begingroup$ @D.W. I considered a set for $S$, is it enough to calculate the max in $O(1)$? $\endgroup$
    – kik
    Commented Apr 12, 2018 at 12:27

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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