Week 1 Flashcards
Define Time Complexity
It is a measure of the amount of time an algorithm takes to complete as a function of the length of the input.
Big O Notation
Define Space Complexity
It is the total amount of memory that an algorithm or operation needs to function relative to the size of the input data.
It can be expressed using Big O Notation
What do we intend the algorithm to do?
Be detailed and precise such as constraints, edge cases and handling errors
Define Pre-conditions
Conditions or rules that must be true before the execution of an algorithm or a function.
Such as an array must be sorted first
Define Post-Conditions
Conditions that must be true after the execution of an algorithm or a function.
Define Invariants
It is a condition that remains true throughout the execution of an algorithm.
It make sure the algorithm or data structure maintains its integrity and behaves as expected
What are the steps for algorithm design?
- Specification - what you want it to do and write it down
- Think, come up with an idea and write down your algorithm step by step
- Check if the algorithm does satisfy the specification (post-conditions and invariants)
- If necessary, check the Time and Space Complexity
What is the specification for a linear search?
How to perform an algorithm for linear search?
- Start from the beginning: begin at the first element of the list
- Compare each element: Compare the current element with the value you are searching for
- Match Found: If the current element matches the search value, return the index of the this element indication the position of the value within the list
- Move to the Next element: if the current element is not a match, move to the next element in the list
- Repeat the process: Continue steps 2-3 until either find a match or reach the end of the list
- End of List: If you reach the end of the list without finding a match, the search value is not in the list and returns -1 as the result.
What’s the pre-conditions to perform a linear search?
- The list to be searched is accessible and not null
- The value to be searched for is defined and comparable with the elements in the list
- The list does not necessarily need to be sorted
What is the invariant of performing a linear search?
The part of the list that has been searched does not contain the target value. This is maintained through the execution of the algorithm.
What’s the post-conditions of performing a linear search?
- If the target value is in the list, the algorithm returns the index of the first occurrence of the value
- If -1 is returned, then the target value is not in the list
- The list remains unchanged after the execution of the algorithm
