Studied by 3 people
Time Complexity
A computational complexity that describes the amount of time an algorithm takes to complete as a function of the length of the input.
Big O notation
is a mathematical notation used to classify algorithms according to their worst-case or upper-bound performance in terms of time or space relative to the input size.
O(1)
Describes an algorithm that executes in constant time, regardless of the size of the input data.
O(n)
Describes an algorithm whose performance will grow linearly and in direct proportion to the size of the input data.
O(n2)
Describes an algorithm whose performance will grow in proportion to the square of the size of the data set, often seen in algorithms with nested iterations. Known as polynomial time complexity.
O(2n)
Describes an algorithm whose performance grows exponentially with the size of the input data, doubling with each additional element.
O(log n)
Describes an algorithm whose performance increases logarithmically as the size of the input data increases, often seen in divide-and-conquer algorithms like binary search.
Linear Search
A simple search algorithm that checks each element in a list sequentially until the target value is found or the list ends. It has a time complexity of O(n).
Binary Search
A search algorithm that finds the position of a target value within a sorted array by repeatedly dividing the search interval in half. It has a time complexity of O(log n).
Divide and Conquer
A problem-solving strategy that breaks a problem into smaller subproblems, solves each subproblem independently, and combines their solutions to solve the original problem. This approach is commonly used in algorithms such as merge sort and binary search.
Recursive algorithm
A method of solving problems where the solution depends on solutions to smaller instances of the same problem, typically involving a function that calls itself.
Binary Tree search
A method for searching data in a binary tree structure, where each node has at most two children, typically using a depth-first or breadth-first traversal approach.
Bubble Sort
A simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. This process is repeated until the list is sorted. It has a time complexity of O(n²) in the worst case.
Insertion Sort
A sorting algorithm that builds a sorted array one element at a time by repeatedly taking the next element from the unsorted portion and inserting it into the correct position in the sorted portion. It has a time complexity of O(n²) in the worst case but can be close to O(n) if the list is nearly sorted.
Merge Sort
A divide-and-conquer sorting algorithm that recursively splits the list into smaller sublists, sorts them, and then merges the sorted sublists back together. It has tine complexity of O(n log n) in all cases.
Quick Sort
A highly efficient sorting algorithm that uses a divide-and-conquer approach. It selects a 'pivot' element, partitions the array into elements less than and greater than the pivot, and recursively sorts the partitions. It has time compexity of O(n log n) on average.
Space complexity
refers to the amount of memory space required by an algorithm to run as a function of the size of the input data. It is typically expressed in terms of big O notation.
Depth first traversal
A graph traversal algorithm that explores as far as possible along each branch before backtracking. It can be implemented using recursion or a stack.
Breadth first traversal
A graph traversal algorithm that explores all neighbors at the present depth prior to moving on to nodes at the next depth level. It is typically implemented using a queue.
Adjacency list
A data structure used to represent a graph, where each vertex has a list of other vertices it is directly connected to. This allows for efficient storage and traversal of sparse graphs.
Applications of breadth first search
include finding the shortest path in unweighted graphs, peer-to-peer networking, and web crawling.
Applications of depth first search
include topological sorting, pathfinding in mazes, and solving puzzles like Sudoku.
Dijkstra’s Shortest Path Algorithm
A graph search algorithm that finds the shortest path from a starting vertex to all other vertices in a weighted graph, using a priority queue to explore the nearest vertices first.
Optimisation Problems
Problems that require finding the best solution from a set of feasible solutions, often involving minimizing or maximizing a function. Examples include scheduling flights to allow crews to have at least minimum rest time, finding the best move in chess, timetabling classes in schools and finding the shortest path between two points.
A* Algorithm
An informed search algorithm that finds the shortest path from a start node to a target node by using heuristics to estimate the cost of reaching the goal.
Cost function
A function that quantifies the cost associated with a particular path or solution in optimization problems, often used to guide algorithms like A* in finding the shortest path.
