OCR Computer Science AS Level: Analysis, Design and Comparison of Algorithms Study Notes

When developing an algorithm, there are two primary factors that must be evaluated:
- Time Complexity
- Space Complexity

Time complexity is defined as the amount of time an algorithm requires to solve a specific problem.
Effectiveness of an algorithm is measured using Big O notation.
Big O notation represents the amount of time taken relative to the number of data elements ( $n$ ) provided as input.
The utility of Big O notation lies in its ability to allow developers to predict the total time an algorithm will take to finish based on the volume of data elements.

Constant Time Complexity ( $O(1)$ ):
- The amount of time required to complete the algorithm is entirely independent of the number of elements inputted.
Linear Time Complexity ( $O(n)$ ):
- The amount of time taken to complete the algorithm is directly proportional to the number of elements inputted.
Polynomial Time Complexity ( $O(n^2)$ , $O(n^n)$ ):
- For the example $O(n^2)$ , the time taken is directly proportional to the square of the elements inputted.
- For the example $O(n^n)$ , the time taken is directly proportional to the elements inputted raised to the power of $n$ .
Exponential Time Complexity ( $O(2^n)$ ):
- The time taken to complete the algorithm doubles with every additional item added to the input.
Logarithmic Time Complexity ( $O(\log(n))$ ):
- The time taken to complete the algorithm increases at a progressively smaller rate as the number of elements inputted grows.

A logarithm acts as the inverse of an exponential operation.
It is a mathematical operation that determines how many times a base number must be multiplied by itself to reach a specific target number.
Relationship between $x$ and $y = \log(x)$ (assuming base 2 in this context):
- If $x = 1$ (which is $2^0$ ), then $y = 0$ .
- If $x = 8$ (which is $2^3$ ), then $y = 3$ .
- If $x = 1024$ (which is $2^{10}$ ), then $y = 10$ .

Space complexity refers to the total amount of storage space an algorithm occupies during execution.
Like time complexity, space complexity is commonly expressed using Big O notation ( $O(n)$ ).
Algorithms often generate extra data when making copies of existing data structures; this is considered non-ideal.
When processing large datasets, making copies should be avoided because the resulting storage requirements are expensive.

An algorithm is defined as a series of steps designed to complete a specific task.
Primary Objective: Successfully complete the intended task.
Secondary Objectives: Achieving the best possible time complexity and the best possible space complexity.
Trade-offs: There is often a conflict between minimizing time complexity and minimizing space complexity. The decision of which to prioritize depends entirely on the specific requirements of the situation.
Reducing Space Complexity: Perform all data transformations and changes directly on the original pieces of data to avoid the overhead of copying.
Reducing Time Complexity: Minimize the use of embedded (nested) for-loops as much as possible.
Efficiency Strategies: Reduce the total number of items that require operations. One effective method is the "divide and conquer" approach, which results in a logarithmic algorithm ( $O(\log(n))$ ).

Linear Search Algorithm:
- This algorithm traverses through every item in a list one at a time until the target item is located.
- Big O notation: $O(n)$ .
Binary Search Algorithm:
- This is a "divide and conquer" algorithm.
- It functions by repeatedly splitting the list into smaller sub-lists until the target item is found.
- Because the size of the searchable list is halved during every step, it has a Big O notation of $O(\log(n))$ .
Bubble Sort Algorithm:
- This algorithm makes multiple passes through a list to evaluate pairs of adjacent items.
- It ensures that the larger value in a pair is placed "above" (after) the smaller value.
- It has a polynomial Big O notation of $O(n^2)$ .