Answer 2.2-3 and 2.2-4

1 files changed, 25 insertions, 0 deletions

diff --git a/notes.md b/notes.md
index a8ba4c4..e8d0064 100644
--- a/notes.md
+++ b/notes.md
@@ -483,3 +483,28 @@ the rate of growth in determining computational efficiency for large inputs.
     Give the best-case and worst-case running times of selection sort in 𝚯-notation.
 
       = 𝚯(n^2). two loops, one nested within the other.
+
+2.2-3:
+
+> Consider linear search again (see Exercise 2.1-3). How many elements of the
+> input sequence need to be checked on the average, assuming that the element
+> being searched for is equally likely to be any element in the array? How about
+> in the worst case? What are the average-case and worst-case running times of
+> linear search in 𝚯-notation? Justify your answers.
+
+    How many elements of the input sequence need to be checked on the average, assuming that the element being searched for is equally likely to be any element in the array?
+
+      Since there are `n` elements the average would be in the middle (.i.e. n/2).
+      When we drop the lower order terms this becomes `𝚯(n)`.
+
+    How about in the worst case?
+
+      = 𝚯(n). In the worst case you need to search check every element in the input.
+
+    What are the average-case and worst-case running times of linear search in 𝚯-notation?
+
+      They are both 𝚯(n).
+
+2.2-4: How can we modify almost any algorithm to have a good best-case running time?
+
+    Reduce the input size by rejecting elements or hard code an early return if some condition is satisfied.