1
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ no its not a duplicate. Kindly delete your comment. Ty :). Its misleading. My problem is specific. That problem is not. $\endgroup$ – Vk1 Dec 21 '18 at 9:08
  • $\begingroup$ What have you tried? Where did you get stuck? Hint: Try to find a recurrence relation which holds for arbitrary $i$. $\endgroup$ – dkaeae Dec 21 '18 at 9:08
  • $\begingroup$ Sorry, was a bit trigger happy at seeing the question title :) $\endgroup$ – dkaeae Dec 21 '18 at 9:09
  • $\begingroup$ 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? $\endgroup$ – neerajdorle Dec 21 '18 at 9:11
  • $\begingroup$ 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)$... $\endgroup$ – dkaeae Dec 21 '18 at 9:13
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$

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.