8.1 Algorithms (OCR A Level Computer Science) Flashcards

Linear time refers to an algorithm whose number of instructions grows proportionally with the size of the input; this is usually written as O(n).

It means that the number of instructions executed grows proportionally with the input size, so if the input doubles, the execution time also roughly doubles.

In a linear time algorithm, if the input size increases from 100 to 1000, the number of instructions executed will increase by 10 times.

False.

As n increases, the linear term (e.g., 3x) dominates and the constant term becomes insignificant in determining time complexity.

Polynomial time complexity is when an algorithm's performance is proportional to the input size raised to a power, such as O(n²), O(n³), etc.

True.

Bubble sort requires nested loops, resulting in O(n²) time, which is polynomial.

As the value of x increases, the term x² becomes the most significant in polynomial time algorithms.

Each additional nested loop increases the power of n in the Big-O notation, such as O(n²), O(n³), and so on.

Logarithmic time complexity describes an algorithm whose execution time increases very little as the input size grows larger, typically measured as O(log n) in computer science, often using base 2.

False.

In a logarithmic time algorithm, doubling the input size increases the number of instructions by only a small amount, such as one extra step in a binary search.

The worst case complexity of an algorithm is the scenario in which it performs at its least efficient, requiring the maximum number of instructions to complete, such as finding an item in the last position during a linear search or sorting a reversed list with bubble sort.

True.

Big-O notation typically describes the worst case performance of an algorithm so that programmers can guarantee a minimum performance level.

From the Big-O time complexity graph, exponential time grows the quickest and is the most inefficient, while constant time is the most efficient.

In Big-O notation, only the dominant factor is used because as input size grows, coefficients and lower-order terms become insignificant in comparison to the dominant term.

A binary search is an efficient search algorithm that repeatedly compares the middle element of a sorted list to the target value, halving the search space each time until the item is found or not present.

False.

A binary search requires the list to be sorted to work correctly. If the list is not sorted, the algorithm will not function as intended.

The time complexity of a binary search is O(log n), because with each iteration the search space is halved.

An iterative binary search uses O(1) space because it only requires a fixed number of variables. A recursive binary search uses O(log n) space due to the call stack from recursive calls.

The mid pointer identifies the middle element of the current search range, which is compared to the target item to determine if the search should continue to the left or right half of the list.

In a binary search, the list must be ordered before the algorithm can work correctly.

False.

If the middle item is greater than the target, the end pointer is moved to mid - 1.

If the item is not found during a binary search, the algorithm returns -1.

After each iteration, the search range is halved, narrowing down to either the left or right half of the list depending on the comparison result.

A linear search is an algorithm that sequentially checks each element in an unordered list for the target value until it is found or the list ends.

The worst case time complexity of a linear search is O(n), where n is the number of items in the list.

In a linear search, the list is searched sequentially from start to end, comparing each element to the value being searched for.

False.

Linear search works on unordered lists, as it checks each element one by one.

The space complexity of a linear search is O(1), as it only needs a constant amount of extra memory regardless of input size.

If the value being searched for is found in the list during a linear search, the algorithm outputs where it was found.

If the item is not found, linear search returns -1.

In linear search, the variable i is used as a counter to move through the list, and found is a flag to signal when the item is found.

True.

The algorithm breaks out of the loop once the item is found, so it does not continue checking the rest of the list.

The default value of index in linear search is -1, which indicates that the item was not found.

At the start of linear search, index = -1 (indicates not found), i = 0 (counter for the list), and found = False (flag to signal when the item is found) are initialised.

A bubble sort is a sorting algorithm that repeatedly compares and swaps adjacent elements if they are out of order, moving the largest value to the end with each pass.

A pass is a complete cycle through the list where all adjacent pairs are compared and swapped if necessary.

The worst case time complexity of bubble sort is O(n²) and its space complexity is O(1).

False.

If the list is already sorted, bubble sort will only need one pass to check all items, thanks to its swap detection.

True.

Each pass through the list places the next largest value at the end, so the sorted section does not need to be checked in later passes, reducing unnecessary comparisons.

In bubble sort, using a while loop instead of a for loop allows the algorithm to terminate early if no swaps occur.

Early termination in bubble sort is a technique where the algorithm stops if a full pass is completed with no swaps, indicating the list is already sorted.

Decreasing the number of compared items by one on each pass ensures that the already sorted end of the list is not checked again, which improves efficiency by avoiding unnecessary comparisons and swaps.

An insertion sort is a sorting algorithm that sorts one item at a time by placing it in the correct position of an unsorted list, repeating until all items are sorted.

The worst-case time complexity of an insertion sort is O(n²).

Insertion sort is considered to have a space complexity of O(1), as it does not require any additional storage space beyond the input list.

False.

Insertion sort compares the current item to each previous item in the list until it finds its correct position.

False.

In computer science, indexing always starts at 0, not 1.

The insertion sort algorithm compares each item with the values before it in the list to find the correct position.

The statement list[position] = list[position - 1] shifts the previous item one position to the right to make space for the item being inserted in its correct position.

A merge sort is a divide and conquer algorithm that repeatedly divides a list into smaller sub lists until each contains one element, and then merges the sub lists to produce a sorted list.

The two main steps are: first, divide the list into sub lists until each contains only one element; second, repeatedly merge groups of two sub lists and sort them until all have been merged into a single sorted list.

The worst case time complexity of merge sort is O(nlogn), and its space complexity is O(n).

False.

Merge sort can only merge two sub lists at a time during each merging iteration.

In merge sort, recursion means the algorithm calls itself repeatedly to divide the list into smaller sublists until the base case of one element is reached.

In Python, the expression [:mid] returns all elements up to, but not including, the mid index.

In merge sort, leftPointer and rightPointer keep track of the current position in the left and right sublists, while newListPointer keeps track of the next available space in the merged (sorted) list.

False.

Only one of the two final while loops is called, depending on which sublist has remaining elements after the first merge stage.

A quick sort is a divide and conquer algorithm that reduces a problem into smaller subproblems, sorts them recursively using a pivot to partition the list, and combines the results to produce a sorted order.

The pivot in quick sort divides the list into two parts: values less than the pivot and values greater than the pivot. Each sublist is then sorted recursively.

Quick sort has a best and average case time complexity of O(n log n), and a worst case time complexity of O(n²).

False.

In the worst case, if the pivot is always the smallest or largest element, quick sort can take O(n²) time.

The pivot is the element in the list used to compare and partition the other elements during each iteration of quick sort. Typically, it is set to the first element of the sublist.

In quick sort, after the pointers cross, the pivot is swapped with the value indexed by the right pointer.

The left and right pointers are used to scan the sublist from both ends, identifying values that are on the wrong side of the pivot so they can be swapped, ensuring that elements less than the pivot are to its left and elements greater than the pivot are to its right.

True.

Quick sort partitions the list using a pivot, then recursively applies the same process to sublists on either side of the pivot until the entire list is sorted.

Dijkstra's shortest path algorithm is an optimisation algorithm that calculates the shortest path from a starting node to all other nodes in a weighted graph.

Dijkstra's algorithm solves optimisation problems by finding the shortest route between two points or from a start to all other nodes in a network.

In Dijkstra's algorithm, each connection between two nodes is called an arc/edge or node/vertex, and carries a weighted value.

False.

Dijkstra's algorithm calculates the shortest path from the starting node to every other node in the graph.

During Dijkstra's algorithm, unvisited nodes are organised in a priority queue so that the node with the lowest path is always chosen next.

When starting Dijkstra’s algorithm, the starting node is initialised to 0 and all other nodes are set to infinity.

After visiting the starting node, you update each of its neighbours by adding the distance from the starting node to each neighbour.

For each node in Dijkstra’s algorithm, you must keep track of the previous node that offered the shortest route.

True.

A node’s distance is updated only if a path through a neighbour results in a shorter total distance than previously recorded.

An A* search algorithm is a pathfinding algorithm that combines the real cost from the start node with a heuristic estimate of the cost to the goal node, aiming to efficiently find the shortest path.

The purpose of the heuristic function h(x) is to estimate the cost from the current node to the goal node, often using the straight line (Euclidean) distance, helping the algorithm focus towards the goal.

In the A* algorithm, the total cost for each node is calculated as f(x) = g(x) + h(x).

True.

A* search is designed to focus on reaching the goal node and terminates once it is found, while Dijkstra’s algorithm continues until it has calculated the shortest path to every node.

A heuristic in the A* algorithm is a value that estimates the cost or distance from a given node to the goal node.

When initialising the starting node, g(x) should be 0, and f(x) should be equal to h(x) (the heuristic value).

To update a neighbour node in A* search, add the distance from the current node to the neighbour and the heuristic value for the neighbour.

True.

In A* search, tracking the previous node that gave the shortest route is essential for reconstructing the optimal path at the end.