Maximum value of the potential function

Assignment Help Basic Computer Science

Reference no: EM13968360

As a result of a splay, most of the nodes on the access path are moved halfway towards the root, while a couple of nodes on the path move down one level. This suggests using the sum over all nodes of the logarithm of each node's depth as a potential function.

a. What is the maximum value of the potential function?

b. What is the minimum value of the potential function?

c. The difference in the answers to parts (a) and (b) gives some indication that this potential function isn't too good. Show that a splaying operation could increase the potential by 8(N/ log N).

Reference no: EM13968360

Questions Cloud

Dividends are in which category of the chart of accounts : Which concept would not be considered if you were to compare the price of a Camaro in 1979 with the price of a Camaro in 2009?

What was so great about alexander the great : What was so "great" about Alexander the Great? What was the significance of the advent of agriculture? Compare and contrast Mesopotamian and Egyptian civilizations.

Deletion procedure for red-black trees : Modify the splay tree to support queries for the kth smallest item. Compare, empirically, the simpli?ed top-down splay with the originally described top-down splay. Write the deletion procedure for red-black trees.

What was role of railroads in the settlement of great west : What was the role of the railroads in the settlement of the Great West? What factors account for the rise of the American steel industry in the late nineteenth century?

Maximum value of the potential function : As a result of a splay, most of the nodes on the access path are moved halfway towards the root, while a couple of nodes on the path move down one level. This suggests using the sum over all nodes of the logarithm of each node's depth as a potenti..

What was remarkable about the american west : What was remarkable about the American West in the late 1800s? Describe the situation facing the Chinese in California in the late 1800s.

Potential of a binomial queue : 1. Show that the binomial queues actually support merging in O(1) amortized time. De?ne the potential of a binomial queue to be the number of trees plus the rank of the largest tree. 2. Suppose that in an attempt to save time, we splay on every secon..

Discuss how the federal government views marijuana use : Discuss how the federal government views/policies marijuana use. Also discuss any large legal cases that involved marijuana.

Consecutive insertions into a binomial queue : 1. When do M consecutive insertions into a binomial queue take less than 2M time units? 2. Suppose a binomial queue of N = 2k - 1 elements is built. Alternately perform M insert and deleteMin pairs. Clearly, each operation takes O(log N) time. Why do..

User Account

All Pages