Amortized algorithm analysis, Data Structure & Algorithms

Assignment Help:

In the amortized analysis, the time needed to perform a set of operations is the average of all operations performed. Amortized analysis considers as a long sequence of operations rather than just one and then gives a worst-case estimate. There are three different methods by which the amortized cost can be calculated and can be differentiated from the actual cost. The three methods are following:

Aggregate analysis: It determines the average cost of each operation. i.e., T(n)/n.

The amortized cost is similar for all operations.
Accounting method: The amortized cost is distinct for all operations & charges a credit as prepaid credit on some of the operations.

Potential method: It also has distinct amortized cost for each of operation and charges a credit as the potential energy to other operations.

There are special operations like stack operations (push, pop, multipop) and an increment that can be considered as instance to verify the above three methods.

Every operation over a splay tree and all splay tree operations take O(log n) amortized time.


Related Discussions:- Amortized algorithm analysis

A full binary tree with 2n+1 nodes, A full binary tree with 2n+1 nodes have...

A full binary tree with 2n+1 nodes have n non-leaf nodes

Representation of a polynomial with a singly linked list, List areutilized ...

List areutilized to maintainPOLYNOMIALS in the memory. For example, we have a functionf(x)= 7x 5 + 9x 4   - 6x³ + 3x². Figure depicts the representation of a Polynomial by means o

Hasing and indexing, differentiate between indexing and hashing in file org...

differentiate between indexing and hashing in file organization

Linked list, How to creat ATM project by using double linked list?

How to creat ATM project by using double linked list?

Multiple stacks in a single array, implement multiple stacks in an array an...

implement multiple stacks in an array and write different algorithms to perform operations on it

Linked List Variations, Part1: Deque and Bag Implementation First, complet...

Part1: Deque and Bag Implementation First, complete the Linked List Implementation of the Deque (as in Worksheet 19) and Bag ADTs (Worksheet 22). Files Needed: linkedList.c Linke

Stack and queue, write a algorithsm in c to perform push and pop operation...

write a algorithsm in c to perform push and pop operations stastic implementation using array ?

Algorithms, Write an algorithm to print all even numbers in descending orde...

Write an algorithm to print all even numbers in descending order and draw the flowchart

Implementation of queue using a singly linked list, Implementation of queue...

Implementation of queue using a singly linked list: While implementing a queue as a single liked list, a queue q consists of a list and two pointers, q.front and q.rear.

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd