4
$\begingroup$

Motivation

So the other day I had fun providing a new solution to this famous question. In the analysis part I showed that my little algorithm has space complexity: O(k) and Ω(log(k)). However, my rough logic says that we should be able to prove a tighter bound of O(min(k,log(n))), but I was unable to prove it. Moreover it seems like an interesting, general-case problem.


To save time for the reader I have changed my space complexity problem to an equivalent complexity problem (the complexity of a function [not of space or time]):

Data:

Array of size k; where elements, e, are unique integers: 0 <= e < n, for some n.

Events:

Find the average (rounded down) of the elements.
Randomly discard either all the elements > than the average, or all the elements <= the average.
We then do the same thing to the reduced array size.
We keep repeating the above steps until the array is size 1.

My Question:

Is it O(min(k,log(n))) on the number of times average is counted? and if so, how do we prove it? (NOTE that we don't care about the time it takes to calculate the average or remove the elements. This is because this questions is deliberately designed to be equivalent to my space-complexity problem.)


My thoughts:

It seems really intuitive that it's O(min(k,log(n))) because if k is n, then taking the average will always divide the elements in half. However, I can't seem to prove that it doesn't sometimes perform worse when k < n.

Thinking about this a bit we recognise that having outliers is really what makes for bad performance, so I try to imagine a worst-case scenario:

array = [1, 2, ..., (x-2), (x-1), (n-1)], where (x-1) < average < (n-1)

In this scenario, we in worst-case reduce the array size to x-1; however, by increasing k by adding any number of elements, e: (x-1) < e < (n-1), the worst-case array size (for the next iteration) is still x-1.

Moreover:

average = (x(x-1)/2 + n-1)/x

Thinking about the complexity, for a given n, worst case x:

x = average

=> x^2 - x^2/2 + x/2 = n-1
=> O(x) = O(sqrt(n))

and here x represents the biggest sub-size.

So in this artificial "worst case" scenario, we get O(sub-array size) = O(min(k,sqrt(n))), which kind of implies that the overall complexity = O(min(k,log(sqrt(n)))) = O(min(k,log(n))).

However, this proof is quite informal and I'm not sure how to show that this genuinely represents the worst-case scenario.

$\endgroup$
9
  • $\begingroup$ Can you be more precise? What do you mean by the number of times average is counted, since this is a randomized algorithm? Do you mean the worst case? (probably not) The average case, i.e., the expected value? $\endgroup$
    – D.W.
    Oct 13 '20 at 2:30
  • $\begingroup$ @D.W. it’s big-O, so yes, it’s worst-case. If you have a look at the next section then I think I provide a good argument for why this seems to be true, but I’d be happy to hear an argument as to why I’m wrong. $\endgroup$
    – Elliott
    Oct 13 '20 at 4:44
  • $\begingroup$ @D.W., my “worst-case” example is trying to engineer exactly that scenario, but still ends up $O(\lg n)$. However, if you provide a solid argument that I’m wrong, then I’ll accept it as an answer. $\endgroup$
    – Elliott
    Oct 13 '20 at 5:10
  • $\begingroup$ @D.W., another way to argue my case is: Equal amount of elements about the mean trivially makes for a $O(\lg n)$ situation. Non-equal amounts can be produced by a skewed distribution. If we choose the region that includes the outliers, then we are doing even better than before (this is less than half), but if we choose the bigger region then we have potentially removed only one element, but it was the outlier. If you want to build a problem that worst-case removes one then each of the values in k have to grow (i think exponentially) to achieve this. But k is bound by n. $\endgroup$
    – Elliott
    Oct 13 '20 at 5:27
  • 1
    $\begingroup$ I take it back. I don't have a counterexample. Sorry. I didn't think about it carefully enough. $\endgroup$
    – D.W.
    Oct 13 '20 at 6:02
2
+50
$\begingroup$

We introduce a weight measure for $S$, a set of numbers with respect to its average, namely: $w(S) = \sum_{s\in S} |s-avg(S)|$. The measure $w(S)$ expresses the total distance to the average. Based on this weight we will prove the number of iterations is in $O(\log\ n)$.

If we apply one iteration of your described algorithm on a set $S$ we obtain either the set $S_\leq = \{s \leq avg(S) \mid s\in S\} $ or the set $S_> = \{s>avg(S) \mid s\in S\}$. Now we show that $w(S_\leq)\leq \frac{w(S)}{2}$ and $w(S_>) \leq \frac{w(S)}{2}$. The weight of both sets $S_\leq, S_>$ w.r.t. the old average of $S$ is equal to: $$\sum_{s\in S_\leq} |s-avg(S)| = \sum_{s\in S_>} |s-avg(S)| = \frac{w(S)}{2},$$

which follows from the observation that $$\sum_{s\in S} (s - avg(S)) = \sum_{s\in S} s - |S|*avg(S) = \sum_{s\in S} s - \sum_{s\in S} s = 0.$$

By the construction of the sets $S_\leq$, $S_>$ only contain negative, and positive terms in $s-avg(S)$, and their sum is the total.

Note that $w(S_\leq) \leq \sum_{s\in S_\leq} |s-avg(S)|$ since $avg(S_\leq)\leq avg(S)$ and symmetrical for the other case.

To complete the complexity bound we confirm that

  • $w(S)\in O(n^2)$ initially since $S\subseteq\{0,\dots,n-1\}$.
  • if $w(S)\leq 1$ it is a base case in $O(1)$ (only 1 more split).
$\endgroup$
8
  • $\begingroup$ I'm just reading the proof now. I'm not sure how crucial this is to your proof, but in the second paragraph you say When 𝑆=1,…,𝑛 is the full set this means 𝑤(𝑆)=(𝑛+1)∗𝑛/2, but this doesn't make sense to me, because we're summing the distances to the middle (where the average is), so it will be roughly 2*((([n-1]/2)+1)∗([n-1]/2)/2) = (𝑛+1)∗(𝑛-1)/4 [this is assuming that n is odd, and so the middle number doesn't contribute to the total (hence the -1). We sum to the middle, and multiply by two because of symmetry] $\endgroup$
    – Elliott
    Sep 1 at 14:52
  • $\begingroup$ And if n is even we get: 𝑤(𝑆) = 2*((([𝑛-2]/2)+1)∗([𝑛-2]/2)/2) + 𝑛∗(1/2) = 𝑛(𝑛-2)/4 + 𝑛/2 $\endgroup$
    – Elliott
    Sep 1 at 15:00
  • 1
    $\begingroup$ Thanks for reviewing it. It still doesn't matter, but the 𝑤(𝑆)=⌈𝑛/2⌉^2 (with 0 added to the set) doesn't seem to be right either: 𝑛 = 4 => 𝑤(𝑆) = 2(2 + 1) = 6 != 4 = ⌈𝑛/2⌉^2. Technically the original problem was defined as 𝑆 = {0, 1, ..., 𝑛-1} (so, non-inclusive of 𝑛) which means the formulas above should still work for 𝑤(𝑆) (each element being reduced by one has no effect). However, I think we can avoid all this arithmetic by replacing with the obvious: 𝑤(𝑆) ∈ 𝑂(𝑛^2) $\endgroup$
    – Elliott
    Sep 2 at 9:37
  • 1
    $\begingroup$ An ingenious measure that captures OP's intuition! $\endgroup$
    – John L.
    Sep 2 at 21:57
  • 1
    $\begingroup$ In fact, this answer has proved that the number of iterations needed when $S\subseteq\{0,1,\cdots, n-1\}$ is at most $2\log_2 n -1 $. $\endgroup$
    – John L.
    Sep 2 at 22:14

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.