# Questions tagged [amortized-analysis]

A method in analysis of algorithms that considers the overall cost of a sequence of operations.

127 questions
Filter by
Sorted by
Tagged with
19 views

### Amortized Analysis of extract-min-operation of Fibonacci Heap

I am studying the operations of the Fibonacci heap. While going through min-extraction operation every step and its complexities are fairly clear to me. In short, it is: The potential before ...
41 views

### Analyzing Hybrid Merge and Insertion Sort

We know that merge sort takes O(n log n) and insertion sort takes (n^2) for worst case. The combination of these two algorithm is to speed up and reduce key comparisons, as for a subarray with small ...
24 views

### Amortized cost depending on the number of operations

Considering a dynamic array that grows by a constant factor $k$ (the new array has $k$ more cells than the last one) each time the array is full which initially has $n$ elements in it. Calculating the ...
176 views

### A formal definition for amortized time

Several (tutoring) students have asked me for a formal definition of amortized time and I've never been able to find one online. All the literature I've found usually outlines the three most common ...
42 views