3.4 Practice Problems
Let's consolidate our learning with some practice problems. These problems are designed to help you think about how algorithms work and to practice analyzing their efficiency in terms of time and space complexity. For each problem, try to write the pseudocode, determine the time and space complexity, and explain your reasoning.
Linear Search:
- Implement a function linear_search(list, item) that takes a list and an item, and returns the index of the item if it is found in the list, and -1 otherwise.
- Example input: linear_search([1, 3, 5, 7, 9], 5)
- Example output: 2
- Think about: What is the time and space complexity of your implementation?
Solution:
This problem can be solved by iterating through the given list and checking if each item is equal to the target item.
Time Complexity: O(n) - In the worst-case scenario, we need to look at each item in the list.
Space Complexity: O(1) - We are not creating any new data structures that grow with the size...