Show that the following algorithm takes $O(n)$ time
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$.