1
$\begingroup$

I'm trying to find time complexity $T(n)$ of the algorithm by a given pseudocode:

1: for i:=1 to N do
2: begin
3:   len := 1
4:   while i - len >= 1 and i + len <= N do
5:   begin
6:     if a[i] > a[i - len] and a[i] > a[i + len] then
7:       len := len + 1
8:     else
9:       break
10:   end
11:   print(i, len)
12: end

I know that the answer is $T(n) = O(n\log n)$ but I struggle to prove that.

From the pseudocode its clear that this algorithm is designed to find the longest subarray with each element smaller then the middle one. (actually this algorithm prints the length of such array for each array element)

I can't prove it formally because I struggle with the content-dependent loop at 5-10, but informally I went like this: Lets construct the array which will be the worst case for this algorithm.

For the sake of simplicity lets use array with 15 elements and start with array filled with zeros: $$0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0$$ external loop will execute 15 times and each time the loop 5-10 will perform a single comparison Now we will do the following: we divide array in two and put maximum value in the middle. Then for each half we will do the same, except the value will be decresed by 1.

We will get the following array: $$0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0$$

Now, intuitively I can see why this is the worst case for the algorithm and where $logn$ comes from, but I can't prove it properly.

As a side note I would appreciate any pointers toward where one can practice these kind of problems (concrete algorithms time complexity analysis, preferably with answers/explanations)

$\endgroup$
  • $\begingroup$ cs.stackexchange.com/q/23593/755 $\endgroup$ – D.W. Jun 1 '17 at 0:08
  • $\begingroup$ Thanks, I've studied that page (which is great), but couldn't apply the methods here, thats why I've created the question $\endgroup$ – Igor Korotkov Jun 1 '17 at 0:19
  • 1
    $\begingroup$ That page describes a systematic approach, where the first step involves writing down recurrence relations that characterize the running time. The translation from code to recurrence relations is fairly mechnical. Have you tried applying that? How far did you get? $\endgroup$ – D.W. Jun 1 '17 at 0:21
  • $\begingroup$ Possible duplicate of Is there a system behind the magic of algorithm analysis? $\endgroup$ – David Richerby Jun 1 '17 at 8:21
  • $\begingroup$ How is this a duplicate? As noted, that page describes a systematic approach (which, possibly, can be applied here), however this questions presents a concrete algorithm along with my thoughts and progress here. If method from that question can be applied here - great, I would appreciate some hints on the inner cycle. But it also can be solved by proving that my example is indeed the worst case, and after that, proving the complexity is a matter of solving reccurence relation. If this is a duplicate of that question then any algorithm complexity evaluation question is a duplicate $\endgroup$ – Igor Korotkov Jun 1 '17 at 13:53
1
$\begingroup$

Let an array $a[1],\ldots,a[n]$ be given. For an index $i$, let $\ell(i)$ be the largest $\ell$ such that $\{i-\ell,\ldots,i+\ell\} \subseteq \{1,\ldots,n\}$ and $a[i]$ is larger than all elements $a[i-\ell],\ldots,a[i-1],a[i+1],a[i+\ell]$. It is not difficult to see that the running time of the algorithm on the array is $\Theta(n + \sum_{i=1}^n \ell(i))$.

This prompts the following definition:

Given $n$, the quantity $M(n)$ is the maximum of $\sum_{i=1}^n \ell(i)$ over all arrays of length $n$.

Let $a$ be an array for which $M(n)$ is achieved, and let $a[i]$ be an element of maximum value. Then $\ell(i) = \min(i-1,n-i)$. Moreover, since $a[i]$ is not smaller than any other element, we have $\sum_{j=1}^{i-1} \ell(j) \leq M(i-1)$ and $\sum_{j=i+1}^n \ell(j) \leq M(n-i)$. This shows that $$ M(n) \leq \max_{i=1}^n M(i-1) + M(n-i) + \min(i-1,n-i). $$ In fact it is not hard to check that equality holds: take the maximum $i$, and combine two arrays attaining $M(i-1)$ and $M(n-i)$ with a larger element in the middle. This gives the recurrence $$ M(0)=0, \; M(n) = \max_{i=1}^n [M(i-1) + M(n-i) + \min(i-1,n-i)]. $$ This recurrence is A078903. It is intuitively clear that the best choice for $i$ is $\lfloor \frac{n+1}{2} \rfloor$ or $\lceil \frac{n+1}{2} \rceil$.

We can solve the recurrence explicitly: for $0 \leq k < 2^m$, we have $$ M(2^m+k) = (m-2)2^{m-1}+1+N_2(k), $$ where $N_2(k)$ is the total number of 1s in the binary expansions of $1,\ldots,k$ (this is A000788). It is known that $N_2(k) = k\log_2 k + O(k)$, and so $M(n) = \Theta(n\log n)$. This asymptotic estimate also follows from the monotonicity of $M(n)$, by considering the cases $k = 0$.

We conclude that the running time of the algorithm is indeed $O(n\log n)$, and moreover this estimate is tight.

$\endgroup$
  • $\begingroup$ Thanks, this is great. What is the reason for bringing k in the solving reccurence relation part? Couldn't we assume that the size of the array is $2^m - 1$? We could prove fomally that this doesn't affect the complexity, if needed, by extimating the complexity of $2^m$ and $2^{m-1}$. Then we would have to solve the reccurence relation $M(2^m - 1) = 2M(2^{m-1} - 1) + \Theta(2^m - 1)$ which will give us $M(n) = \Theta(n\log n)$? $\endgroup$ – Igor Korotkov Jun 1 '17 at 14:41
  • $\begingroup$ Unfortunately you can't do that, since the recurrence relies on all values of $M$. We don't know in advance that the rule of choosing $i$ as close as possible to $\frac{n+1}{2}$ is optimal – we have to prove it by induction (or in any other way). $\endgroup$ – Yuval Filmus Jun 1 '17 at 15:41

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.