diff options
| author | mo khan <mo@mokhan.ca> | 2021-09-19 16:32:46 -0600 |
|---|---|---|
| committer | mo khan <mo@mokhan.ca> | 2021-09-19 16:32:46 -0600 |
| commit | 01cc5021f6fb288a509326cc2fd1f5af04528a50 (patch) | |
| tree | 2fa08a271486af725013706ec3649402effa7f20 | |
| parent | d4420cb79a84d0460ddbd1df13ec08c6ca9d77c7 (diff) | |
finish another question in assignment 1
| -rw-r--r-- | 0x01/README.md | 17 | ||||
| -rw-r--r-- | README.md | 4 | ||||
| -rw-r--r-- | notes.md | 3 |
3 files changed, 22 insertions, 2 deletions
diff --git a/0x01/README.md b/0x01/README.md index ee4fe11..60d2bc8 100644 --- a/0x01/README.md +++ b/0x01/README.md @@ -131,6 +131,23 @@ Submit your solutions to the following exercises and problems: about in the worst case? What are the average-case and worst-case running times of linear search in O-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)`. Hence, the term + linear search. + + How about in the worst case? + + In the worst case you need to search check every element in the input. + Because of this the worst case would be equal to the size of the input. + i.e. `𝚯(n)`. + + What are the average-case and worst-case running times of linear search in 𝚯-notation? + + When we drop lower order terms, like constants then they are both `𝚯(n)` + + 1. Exercise 2.3-5 from the textbook (10 marks) Referring back to the searching problem (see Exercise 2.1-3), observe that @@ -83,8 +83,8 @@ When you have completed this objective, you should be able to #### Required Activities -* [ ] Study Section 2.2 of the textbook. -* [ ] Do Exercise 2.2-3 from the textbook as part of Assignment 1. +* [X] Study Section 2.2 of the textbook. +* [X] Do Exercise 2.2-3 from the textbook as part of Assignment 1. For supplemental material, I recommend that you watch this video (please ignore the beginning of the video talking about their course information. You can start from 17:20): @@ -508,3 +508,6 @@ the rate of growth in determining computational efficiency for large inputs. 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. + + +## 2.3 Designing Algorithms |