<p>You may need to look at this report:
<a href="https://www.cs.princeton.edu/~fiebrink/423/AmortizedAnalysisExplained_Fiebrink.pdf" rel="nofollow noreferrer">https://www.cs.princeton.edu/~fiebrink/423/AmortizedAnalysisExplained_Fiebrink.pdf</a></p>

<p>Each individual operation takes $O(\log n)$ but when you apply amortized analysis to a sequence of operations, you get something interesting. </p>

<p>Directly from this report:
"However, amortized analysis can be used to show that any sequence of $m$ insert and delete operations causes $O(m)$ structural modifications in the worst case (Cormen et al. p.428). It can similarly be shown that the total time for  $m$ consecutive insertions in a tree of $n$ nodes is $O(n + m)$ (Tarjan 1985)."</p>

CC BY-SA 4.0
2021-08-02T09:03:46.083Z
So the amortized runtime complexity is constant / O(1)?
David Schumann
CC BY-SA 3.0
2017-10-12T17:00:34.490Z
2017-10-12T17:20:21.200Z
2017-10-12T17:20:21.200Z
Hung Le
<p>Is there an analysis of red-black trees using amortized analysis? I saw it mentioned somewhere as an example of amortized analysis but all the proofs that I know use a global approach ("black height") to demonstrate the O(log n) runtime of individual operations. </p>

<ds.algorithms><binary-trees>
Amortized analysis of red-black trees
Martin Hofmann
# Amortized analysis of red-black trees

(Asked by: username_0 on 2017-10-05)

Is there an analysis of red-black trees using amortized analysis? I saw it mentioned somewhere as an example of amortized analysis but all the proofs that I know use a global approach ("black height") to demonstrate the O(log n) runtime of individual operations.

**Tags:** ds.algorithms, binary-trees


---

## 1 answers

### Answer by username_1 on 2017-10-12. Score: 1

You may need to look at this report:
<https://www.cs.princeton.edu/~fiebrink/423/AmortizedAnalysisExplained_Fiebrink.pdf>

Each individual operation takes $O(\log n)$ but when you apply amortized analysis to a sequence of operations, you get something interesting.

Directly from this report:
"However, amortized analysis can be used to show that any sequence of $m$ insert and delete operations causes $O(m)$ structural modifications in the worst case (Cormen et al. p.428). It can similarly be shown that the total time for $m$ consecutive insertions in a tree of $n$ nodes is $O(n + m)$ (Tarjan 1985)."

> **Comments:**
> **username_2**: So the amortized runtime complexity is constant / O(1)?  

---

