Download the included file "exercise6.py" and complete both functions.
Part 1
The function findValley() should run in O(log(n)) time where n is the size of the list (hint: divide and conquer, i.e., what underlies merge sort and many other recursive algorithms).
Trivial solutions that run linear time will not receive any marks.
Warning: if your code performs a list slice (something like l[:k] or l[k:]) then it is probably taking linear time! In particular, list slice unfortunately makes a full copy of the sliced portion of the list.
Part 2
For full marks, the function climbing() should run in O(n * log(limit)) time where limit is the last parameter of the function and n is the length of the list.
(hint: can you at least check if a proposed value for the value of 'burst' is sufficient to reach the top in the given time limit?)
Feel free to change the docstring comments for both functions if you want. They are very long. You do not need docstring tests.
Submit your completed implementation of both functions (along with any helper functions you want) in a single file exercise6.py and upload it. Do not zip it. Remember to adhere to the code submission guidelines, including helpful comments describing your solution with useful variable names.
2 of 2 , 1:03 p.m.
