this is for holding javascript data
Xavier Holt edited Line_Segments_Algorithm_and_Runtime__.md
about 8 years ago
Commit id: 520d076632747e3885fde9b69d7faf3ef401121d
deletions | additions
diff --git a/Line_Segments_Algorithm_and_Runtime__.md b/Line_Segments_Algorithm_and_Runtime__.md
index cb432f6..ae987c7 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\left(\frac{n}{n}\right) =
O(1)). O(1)\). This ensures overall \(O(n)\) runtime \(\square\).
## Correctedness