this is for holding javascript data
Xavier Holt edited Line_Segments_Algorithm_and_Runtime__.md
about 8 years ago
Commit id: 8894e0d676f27a9a3f02082775cdc9341f4f12f6
deletions | additions
diff --git a/Line_Segments_Algorithm_and_Runtime__.md b/Line_Segments_Algorithm_and_Runtime__.md
index 0dd1ac1..cb432f6 100644
--- a/Line_Segments_Algorithm_and_Runtime__.md
+++ b/Line_Segments_Algorithm_and_Runtime__.md
...
- Emit index of `s` or 0 in the empty case: \(O(1)\).
- Push `i` onto `S`: \(O(1)\).
To see that our pop-step is amortised \(O(1)\) we note that every element is pushed onto our stack at most one time. We can only pop as many elements as we push, so in total we can pop \(O(n)\) elements. Our loop runs \(O(n)\) times, so the amortised pop-step per iteration is \(\frac{O(n)}{O(n)} =
O(1) \square\). O(1)). This ensures overall \(O(n)\) runtime \(\square\).
## Correctedness