Algorithms and Big O Flashcards
What is Dijkstra’s algorithm?
An algorithm for finding the shortest paths between nodes in a graph
What is A* algorithm?
An algorithm that finds the shortest path from a start node to a target node, using a heuristic to improve performance by prioritising paths that seem more promising
What does the Big O notation do?
It measures the efficiency of an algorithm
What is Big O?
A notation used to describe the performance of an algorithm as the amount of data increases
What is Constant Time Complexity (O(1))?
An algorithm whose execution time remains constant, regardless of the input size.
What is Linear Time Complexity (O(n))?
An algorithm whose execution time grows linearly with the input size.
What is Polynomial Time Complexity (O(n^k))?
An algorithm whose execution time grows proportionally to the input size raised to a constant power.
What is Exponential Time Complexity (O(2^n))?
An algorithm whose execution time doubles with each additional input element.
What is Logarithmic Time Complexity (O(log n))?
An algorithm whose execution time increases at a decreasing rate as the input size grows.
What is Bubble Sort?
A sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order.
What is Insertion Sort?
A sorting algorithm that builds the final sorted array one item at a time, placing each new element in its correct position.
What is Merge Sort?
A divide-and-conquer sorting algorithm that splits the array into halves, recursively sorts them, and then merges the sorted halves back together.
What is Quick Sort?
A divide-and-conquer sorting algorithm that selects a ‘pivot’ element and partitions the other elements into two sub-arrays, recursively sorting them.
What is Binary Search?
An algorithm for finding an item from a sorted list by repeatedly dividing the list in half.
What is Linear Search?
A search algorithm that checks every element in a list until the desired element is found or the list ends.
What is a Heuristic?
A sensible estimate of the distance to the goal node from the current node
