Hi bill, question 6 did ask for complexity as well. Question 6 is asking why your solution is correct as well as the time complexity of your solution. Here is my answer that I got full marks for:
## Question 6 (1 mark)
Give an argument for the correctness and complexity of your `count_time()` function.
>To count the number of entries in leaderboard, we need to search through the ordered list leaderboard and count the number of matching times there are.
>For maximum efficiency, we can use a binary search to find an index for a single instance of matching time, and then iterate above and below that index to count all the instances of the time we are trying to count.
>This is possible as the leaderboard list is sorted, meaning all of the same times will be next to each other.
>To avoid writing a second binary search function that only searches for time, we can modify the binary search function used in submit_run() by allowing the name argument to be optional.
>Only when the name argument is passed will we also search by name.
>There is however a problem with using the same function, in that it wil return an index regardless of whether the time is found or not.
>This can be easily circumnavigated by performing a check and returning a count of 0 if the time of the entry does not match with the time we are trying to count.
>Similarly to submit_run(), to perform the binary search we require O(log2(n)) time as the search range is halved every time
>In the worse case, the time of every run in leaderboard may be the same, so when we search left and right of the found index, we may require O(n) time to count every entry
>However, in this worse case, the binary search would complete in just O(1) time, so we do not need to add these time complexities together for the total complexity
>Hence, the time complexity of this function is O(n) as O(n) > O(log2(n)) as O(n) and O(log2(n)) cannot occur at the same time
>The time taken for binary search O(1) in the worst case and all other insignficant operations get dropped according to asymptotic analysis
>Although the time complexity may seem the same as just iterating through the leaderboard normally, in regular test cases where the leaderboard contains a range of run times,
the binary search will serve to improve efficieny.