1

Edit: This proof is insufficient as pointed out in comment. I am assuming that when the author says "covers the full height of the tree", it means that the node that is put at the root of the tree will be exchanged with one of its children until it reaches a leaf of the tree. Since the heap is a complete tree, it means that its leaves are all on ...


1

The move-to-front heuristic is 4-competitive in the model where swapping adjacent elements costs one unit. This means that if the optimal strategy has cost $N$, then move-to-front has cost at most $4N$. In particular, if a swap list has cost $N$ on some searching sequence, then move-to-front will have cost at most $4N$. See for example MIT OpenCourseWare or ...


1

Let $n = 3^{k}$ to obtain $T(3^{k}) = 9T(3^{k-1}) + 9^{k}$. This can be written $t_{k} - 9t_{k-1} = 9^{k}$. The characteristic equation is $(x-9)^{2} = 0$. Hence $t_{k} = c_{1}9^{k} + c_{2}k9^{k}$. Putting $n$ back instead of $k$, we find $T(n) = c_{1}n^{2} + c_{2}n^{2}\log_{3}n$. $T(n)$ is therefore $\Theta(n^{2}\log_{3}n)$.


Only top voted, non community-wiki answers of a minimum length are eligible