Weak topics

Linear Search Time Complexity

Best: O(1), Average: O(n), Worst: O(n)

Linear Search Space Complexity

Iterative: O(1)

Binary Search Time Complexity

Best: O(1), Average: O(log n), Worst: O(log n)

Binary Search Space Complexity

Iterative: O(1), Recursive: O(log n)

Bubble Sort Time Complexity

Best: O(n), Average: O(n²), Worst: O(n²)

Bubble Sort Space Complexity

Iterative: O(1)

Insertion Sort Time Complexity

Best: O(n), Average: O(n²), Worst: O(n²)

Insertion Sort Space Complexity

Iterative: O(1)

Merge Sort Time Complexity

Best/Average/Worst: O(n log n)

Merge Sort Space Complexity

Recursive: O(n)

Quicksort Time Complexity

Best: O(n log n), Average: O(n log n), Worst: O(n²)

Quicksort Space Complexity

Recursive: O(log n)

Problem Recognition

Identifying that there is a problem to be solved, determining exactly what the problem is from a description or scenario, and deciding whether it can be solved using computational methods

Performance Modelling

Simulating the behaviour of a system before use under load using mathematical models because real testing may be too expensive, unsafe, or time-critical

Visualisation

Presenting data in an easy-to-understand form, often graphically using symbols or objects; simplifies problems through abstraction

Quicksort Process

Choose a pivot; compare each element to the pivot; put items less than the pivot into the left sublist; put items greater than the pivot into the right sublist; choose a pivot in each sublist and repeat until each item becomes a pivot

Tree and Graph Similarities

Both consist of nodes; both are connected by edges; both are non-linear data structures; both can be dynamic data structures

Tree and Graph Differences

Trees have one root node whereas graphs do not require a root node; trees do not allow cycles/loops whereas graphs can contain cycles/loops; trees represent hierarchy whereas graphs do not require hierarchy; trees are typically undirected whereas graphs can be directed or undirected; trees are always connected whereas graphs can be connected or disconnected

Caching

Frequently used data is stored in cache/RAM so it can be accessed more quickly in the future

Caching Benefits

Faster access to data; less CPU idle time; greater instruction throughput

Caching Drawbacks

Complicated to implement effectively due to the need for a suitable caching algorithm

Benefits of abstraction

Reduces programming time

• Reduces complexity of code (through abstraction by generalisation)

• Reduces amount of memory required / computational power

• Simplifies the problem so it's easier to solve / understand (by recognising common patterns)

• Allows programmers to focus on core aspects of the problem