Show that the following algorithm takes $O(n)$ time

Question

You are given a linked list of size $n$. An element can be accessed from the start of the list or the end of the list. The cost to access any location is $\min(i,n-i)$, if the location being accessed is at index $i$ and it belongs to a list of size $n$. Once an index $i$ is accessed, the list is broken into two lists. One list contains the first $i$ elements and the second list contains the rest of the elements. It has something to do with cartesian trees, but I am not clear how to proceed with this chain of thought.

Show that the total cost incurred to access all the elements is any arbitrary order is $O(n)$.

Answer 1

Can't be done.

Consider the following sequence of access: $$\tfrac{1}{2}n, \tfrac{1}{4}n, \tfrac{3}{4}n, \tfrac{1}{8}n, \tfrac{3}{8}n, \tfrac{5}{8}n, \tfrac{7}{8}n, \ldots$$

The first access costs $\tfrac{1}{2}n$. The next two cost $\tfrac{1}{4}n$ each, for a total of $\tfrac{1}{2}n$. The next four also cost a total of $\tfrac{1}{2}n$. Overall we get a cost of $\tfrac{1}{2}n \lg n$.

Answer 2

As mentioned in the other answers, there are counterexamples with cost $c\cdot n \log n$. Here's a quick argument for why the bound $O(n \log n)$ is tight. Let's build a binary tree from the access sequence: when we split at some $i \in [n]$ we make element $i$ the root, and then turn $[1, i-1]$ and $[i+1, n]$ into binary trees recursively using the same procedure. The resulting two trees will be the two children of $i$ (as long as they are non-empty).

Now what was the cost incurred for element $i$? Note that $\min(i, n-i)$ is proportional to the size of the smallest of the subtrees rooted at $l(i)$ and $r(i)$ in the tree we constructed above. So the cost incurred by each element is the size of its smallest child subtree. We can then reverse the question and ask: how often does an element $j$ appear in the smallest subtree of one of its ancestors? When we travel from $j$ to the root, each time this happens, the size of the subtree (at least) doubles, and so this can happen at most $\log n$ times.

Hence the total cost, for any access pattern, is $O(n \log n)$.

Answer 3

We assume that $n=2^k$ ($k\in \mathbb{N_0}$). It must be that the maximum cost to the element that is first accessed is $2^{k}/2$ or $2^{k-1}$, since every other element have less cost than that. After this element is being accessed, the linked list must be broken into two equal size that has size $2^{k-1}$. But then, the maximum cost to access an element for both the linked list is just $2 \times (2^{k-2})=2^{k-1}$. Repeating this again and again, we find that the total cost spent must be $$2^{k-1}+2\cdot2^{k-2}+2^2\cdot2^{k-3}+\ldots+2^{k-2}\cdot2+2^{k-1}=k\cdot2^{k-1}=\mathcal{O}(n \lg n)$$ I don't think that's a $\mathcal{O}(n)$.