5
$\begingroup$

If we can insert to a Fibonacci Heap in O(1), and increase-key and find-min in the same W.C time complexity, then why can't we sort an array in time complexity O(n)?

Given an array with n elements:

  1. Find the maximum of the array (largest key) in O(n).

  2. Build a Fibonacci Heap of the elements in O(n), emptying the array in the proccess.

  3. Use find-min and add the result to the now empty array.

  4. Use increase-key on the element you found in step 3, and increase it by the maximum of the old array + 1 (making it now larger than any element of the old array)

  5. Reapet steps 3 and 4, n times. Each time a new element from the old array is added, because all added elements are larger than max+1.

Improve this question
$\endgroup$
0

2 Answers 2

Reset to default
8
$\begingroup$

Increase-key is not a $O(1)$ operation on Fibonacci heaps. You're thinking of decrease-key.

Exercise: Why can't increase-key be a $O(1)$ operation on this data structure?

Improve this answer
$\endgroup$
2
  • $\begingroup$ Because you must reorder the heap which is not O(1) (?) $\endgroup$
    – Niklas Rosencrantz
    Commented Nov 23, 2017 at 17:13
  • $\begingroup$ It's not a question of reordering the heap. The problem is that if you increase-key the minimum element, it may take a non-constant amount of time to find the new minimum element. It's constant time for decrease-key. $\endgroup$
    – Pseudonym ♦
    Commented Nov 23, 2017 at 23:33
0
$\begingroup$

If it was possible, Heapsort would take $\Theta(n)$ time. This is a contradiction to the lower bound of $\Omega(n\lg n)$ when sorting by comparisons.

Improve this answer
$\endgroup$
1
  • $\begingroup$ This doesn't answer the question. The OP knows its a contradiction, but wants to know what's wrong with his logic. Even if the OP thought his algorithm was real, an independent proof of how the algorithm must be wrong doesn't help locate the error in his argument. "1 > 0" is not an answer to "What is wrong with this proof that 0 = 1?" $\endgroup$
    – Nicholas Pipitone
    Commented Apr 17, 2018 at 22:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.