summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
authormo khan <mo.khan@gmail.com>2020-07-05 15:04:02 -0600
committermo khan <mo.khan@gmail.com>2020-07-05 15:04:02 -0600
commit6c5cbdb6669e7d47103f3ca40bbd2cf8b0895274 (patch)
treecd053231082205241977014786bbff3293efa8f8 /src
parente2999c7387eaa6e179c76f20c40ae8a66bc3f7dc (diff)
Update program profile
Diffstat (limited to 'src')
-rw-r--r--src/01/06/README.md18
1 files changed, 18 insertions, 0 deletions
diff --git a/src/01/06/README.md b/src/01/06/README.md
index c44a3df..bb2d591 100644
--- a/src/01/06/README.md
+++ b/src/01/06/README.md
@@ -11,6 +11,16 @@ as well as the `min()` operation, which returns the minimum value currently stor
All operations should run in constant time.
## Description of the Code
+
+To keep track of the min value, I chose to use two Stacks.
+One stack keeps track of each item that is pushed on.
+The second stack keeps track of each new minimum value that is pushed on to the stack.
+
+`push()`, `pop()` and `size()` are operate in constant time.
+However, `min` operates in constant time until each of the min values
+have been popped off of the min stack. After that it falls back to a linear
+time algorithm to determine the next min.
+
## Errors and Warnings
```bash
@@ -152,3 +162,11 @@ Bye
```
## Discussion
+
+I struggled to find a good algorithm that would guarantee a constant time
+implementation of `min()`.
+
+The worst case scenario for this implementation is when the min value is pushed on to
+the stack right in the center. Half of the pops will would yield a constant time
+implementation of `min()` and the other half would yield a linear time implementation
+of `min()`.