search

nus-cs2103-AY2021S2 / pe-dev-response

0 stars 0 forks source link

Confusing terms used in developer guide - II #290

Open nus-pe-bot opened 3 years ago

nus-pe-bot commented 3 years ago

Note from the teaching team: This bug was reported during the Part II (Evaluating Documents) stage of the PE. You may reject this bug if it is not related to the quality of documentation.

I suspect the author is trying to convey that with brute force approach, the time complexity in the worst case scenario has no upper bounds. Even this statement is misleading because if needed, the time complexity could be calculated to be O(f(x)) for some function f(x). It would be a lot better and more succinct if the author state that the brute force approach is inefficient.

image.png

[original: nus-cs2103-AY2021S2/pe-interim#290] [original labels: severity.Medium type.DocumentationBug]

nowknowing commented 3 years ago

Team's Response

Thank you for your suggestion requesting for better explanations. I think it is valid and agree that I could have been more detailed in my explanations. However, I believe this is an issue not in the scope of DG bugs; it is a request for more comprehensive explanations, which might be something I indeed am not yet able to do (haven't formally learnt about NP).

On a separate note, I hope to share with you that your second and third sentences are false, as I think.

  1. I am quite certain the time complexity cannot be bounded by f(x); it is in fact non-determinable.The approach taken in the brute-force method is to verify if two dates overlap by continuously adding the respective intervals when any date fall behinds the other, until they overlap. This "checking for overlap" indeed does not have bounds. The algorithm in our application's current implementation stops, because we don't only check for overlap (the topic of we discuss right now), but also check if it is out of bounds of the end-date.
  2. "Inefficient" will be a wrong word choice. There are many cases, and in fact most, where the brute-force approach-implementing solution gives a better time than the mathematical method. This is because the extended euclidean algorithm in the mathematical approach is time consuming. In fact, it ia because the brute-force method is more efficient in the imaginable constraints that is a human user, that we take the brute-force approach.

Duplicate status (if any):

--