Problem regarding the complexity of algorithm

Assignment Help Basic Computer Science

Reference no: EM13968207

1. Each deleteMin operation uses 2 log N comparisons in the worst case.

a. Propose a scheme so that the deleteMin operation uses only log N + log log N + O(1) comparisons between elements. This need not imply less data movement.

b. Extend your scheme in part (a) so that only log N + log log log N + O(1) comparisons are performed.

c. How far can you take this idea?

d. Do the savings in comparisons compensate for the increased complexity of your algorithm?

2. If a d-heap is stored as an array, for an entry located in position i, where are the parents and children?

Reference no: EM13968207

Questions Cloud

Why shouldn''t we restrict imports of goods : Some people have said that this shows a double standard: If we're willing to restrict goods on these grounds, why shouldn't we restrict imports of goods that are produced with badly paid labor? Why is or isn't this argument valid?

Algorithm to merge the two heaps : a. Give an O(log N) algorithm to merge the two heaps if l = r. b. Give an O(log N) algorithm to merge the two heaps if |l - r|= 1. c. Give an O(log2 N) algorithm to merge the two heaps regardless of l and r.

Brief overview of the organizations services : Brief overview of the organizations service/products and a description of their target market. This is important to ensure that your analysis considers the needs of the target market in evaluating their pricing and channel decisions

Power company to environmental-sustainability coordinator : After you complete your degree, you are hired by The Peddle Power Company to be their Environmental/Sustainability Coordinator. This is a new position for them, in the past they have made sure to comply with environmental rules and regulations and co..

Problem regarding the complexity of algorithm : If a d-heap is stored as an array, for an entry located in position i, where are the parents and children?

For the soon-to-be-incorporated firm of ebroadcast sports : Dennis is a promoter for the soon-to-be-incorporated firm of eBroadcast Sports, Inc. Dennis signs a contract with Fitz & Geraldo, Accountants, to render their services before eBroadcast Sports is incorporated and for one year after the incorporation.

Running time of both algorithms for sorted : Compare the running time of both algorithms for sorted, reverse-ordered, and random inputs.

Marketing decision that results in dramatic decrease : Donatello is a director and officer of Enzio's Pizza Corporation. Donatello selects an ad campaign that consumers find offensive? a marketing decision that results in a dramatic decrease in profits for the firm and its shareholders. Donatello is a di..

Expected depth of the kth smallest element : Show that the expected depth of the kth smallest element in a large complete heap (you may assume N = 2k - 1) is bounded by log k.

User Account

All Pages