-1

The height of the binary tree keeps reducing every time we remove a root element. Why do we use n (the total number of elements) times logn (the amount of swaps every time we remove a root element) to calculate the total time complexity while the amount of swaps actually varies depending on how many elements remain?

It seems like the correct expression of the time complexity should be the sum of swaps happened for every iteration of root element removal. The amount of swaps would be log(i). i is the remaining elements, and log(i) is the binary tree depth/time complexity/amount of swaps for the removal of each element. i ranges from 1 to n. The sum from log(1) to log(n) would just be O(log(n!)), which is smaller than the expected complexity O(nlog(n)). I would really appreciate it if anyone can explain this.

KATAL
  • 3
  • 1
  • 1
    "The height of the binary tree keeps reducing every time we remove a root element." This is not true, otherwise you could only remove log(n) of the n elements. – Scott Hunter Nov 10 '22 at 19:14
  • 1
    I'd like to see your proof that O(log(n!)) is smaller than O(n log n). – Kelly Bundy Nov 10 '22 at 19:18
  • What I mean is the number of elements we still consider for swapping. In an extreme case, after we sort (n-3) elements, the remaining tree still has log2(n) layers, but only the top two layers would be considered for swapping. – KATAL Nov 10 '22 at 19:19
  • nlogn equals log(n^n), O(n^n) is greater than O(n!), so O(log(n^n)) is greater than O(log(n!)) if I calculated correctly. – KATAL Nov 10 '22 at 19:26
  • Why do you claim that O(log(n!)) is smaller than O(n log n)? They are equal. – kaya3 Nov 10 '22 at 19:37
  • @kaya3 See the comment right above yours. – Kelly Bundy Nov 10 '22 at 19:38
  • Actually I found my deduction a little bit wrong from this [post](https://stackoverflow.com/questions/8118221/what-is-ologn-on-and-stirlings-approximation?noredirect=1&lq=1). It seems like we cannot just apply the log function to O(n!) < O(n^n) and claim that the relationship still holds true. – KATAL Nov 10 '22 at 19:51

1 Answers1

1

There are at least two ways to look at this:

A complete binary tree has O() leaves.

Imagine a heap with 31 elements. This represents a perfect binary tree -- the bottom level is full. The bottom level has 16 elements, (+1)/2. That means in the worst case the next 16 deletions will represent the same number of swaps.

Generalising, to remove about half of the nodes, we need to perform O(/2 log) swaps, i.e. O(log)

O(log!) = O(log)

See this Q&A for a proof.

trincot
  • 317,000
  • 35
  • 244
  • 286