It's UWAweek 17 (1st semester, week 8)

help2200

This forum is provided to promote discussion amongst students enrolled in CITS2200 Data Structures and Algorithms.

Please consider offering answers and suggestions to help other students! And if you fix a problem by following a suggestion here, it would be great if other interested students could see a short "Great, fixed it!"  followup message.

How do I ask a good question?
Displaying selected article
Showing 1 of 95 articles.
Currently 1 other person reading this forum.


 UWA week 17 (1st semester, week 8) ↓
SVG not supported

Login to reply

👍?
helpful
8:00pm Tue 23rd Apr, Lewei X.

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.

The University of Western Australia

Computer Science and Software Engineering

CRICOS Code: 00126G
Written by [email protected]
Powered by history
Feedback always welcome - it makes our software better!
Last modified  5:07AM Sep 06 2023
Privacy policy