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

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)$$.

• no its not a duplicate. Kindly delete your comment. Ty :). Its misleading. My problem is specific. That problem is not. – Vk1 Dec 21 '18 at 9:08
• What have you tried? Where did you get stuck? Hint: Try to find a recurrence relation which holds for arbitrary $i$. – dkaeae Dec 21 '18 at 9:08
• Sorry, was a bit trigger happy at seeing the question title :) – dkaeae Dec 21 '18 at 9:09
• Good question. Even I am trying to solve it now. I am thinking in to solve it using the divide and conquer method and figure out the recurrence relation. Can the tree diagram for merge-sort's divide step help to solve it? – neerajdorle Dec 21 '18 at 9:11
• Wait, either there is something wrong here or I am missing something: What prevents the worst case from being accessing the list from the largest index repeatedly down to 1? The cost in this case is $O(n^2)$... – dkaeae Dec 21 '18 at 9:13

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$$.

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)$$.

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)$$.