What is the amortized time complexity of the Decrease-Key operation in a Fibonacci Heap?

Show answer

O(1)

Fibonacci Heaps are designed to be 'lazy,' deferring work until absolutely necessary. This allows the Decrease-Key operation to run in constant amortized time, making it faster than the O(log n) time required by a standard Binary Heap.

Would you remember this in 6 months?

Trivia Forge uses spaced repetition so facts stick. Free, no signup needed.

Turn on Algorithms practice →

More Algorithms trivia

What is the amortized time complexity of the 'push' operation for a dynamic array that doubles in size when full?
What is the asymptotic time complexity of finding the Longest Common Subsequence of two strings of length m and n using dynamic programming?
Assuming uniform hashing and a constant load factor, what is the average-case time complexity of searching for an element in a hash table whose collisions are resolved by chaining?
What is the lower bound for the height of a binary search tree with n nodes?
What is the lower bound for the worst-case time complexity of any comparison-based sorting algorithm?
What upper bound does a Red-Black Tree with n internal nodes have on its height?

See all 83 →