Level 43

#### 39 words 0 ignored

Ready to learn
Ready to review

## Ignore words

Check the boxes below to ignore/unignore words, then click save at the bottom. Ignored words will never appear in any learning session.

**Ignore?**

time complexity

how much time an algorithm needs to solve a particular problem, so that it can be compared to other algorithms

permutation

the number of ways of arranging the objects in a set of objects

constant time

O(1) describes an algorithm that takes the same amount of time to execute regardless of the size of the input data set

linear time

O(n) describes an algorithm whose performance will grow in direct proportion to the size of the data set

polynomial time

O(n^2) describes an algorithm whose performance is directly proportional to the square of the size of the data set

exponential time

O(2^n) describes an algorithm where the time to execute will double with every additional item in the data set

logarithmic time

O(log n) describes an algorithm where the time to execute it will grow very slowly as the size of the data set increases

O(n!)

Big-O notation for an algorithm that grows in exponential time, but even faster than O(2^n), e.g. for finding permutations

space complexity

the measure of the maximum amount of memory that is needed at any one time in an algorithm

linear search

a search algorithm that goes through every data item individually to find the required item, needed for lists that aren't ordered

O(n)

time complexity of a linear search

binary search

a search algorithm that repeatedly divides a list in half until the required item is found or the list is of size one, however the list must be sorted

divide and conquer

binary search is an example of the ... strategy, which is the strategy of halving the amount of work to do with every iteration

O(log n)

time complexity of a binary search (and a binary tree search)

binary tree search

a recursive search algorithm where half of a tree or subtree is eliminated each time its root is examined

bubble sort

a basic sorting algorithm that repeatedly compares pairs of adjacent items and swaps them into the correct order

flag

to optimise the bubble sort, a ... can be set and tested on each pass as to whether any swaps were made, as this can indicate if the list is sorted or not

insertion sort

a sorting algorithm that takes a data item and places it in the correct position and repeats this until there are no unsorted items left

O(n^2)

time complexity of bubble and insertion sorts

sorted

the time complexity of an insertion sort is close to O(n) if the list is almost ...

O(1)

space complexity of bubble and insertion sorts

merge sort

a sorting algorithm that uses a divide and conquer approach by repeatedly sorting sublists and merging them until a single sorted list is formed

O(n)

space complexity of merge sort

one element

in the merge sort algorithm, the list is divided into n sublists, where each sublist contains ...

quick sort

a sorting algorithm that uses a divide and conquer approach by repeatedly using pivots and moving lesser values into one partition and greater values into another until the list is sorted

O(n log n)

time complexity of merge sort and quick sort

O(n^2)

time complexity of quick sort in the worst case scenario

O(log n)

space complexity of quick sort

stack

quick sort uses recursion, meaning it requires memory space for the ... for each recursion

depth-first traversal

the method of traversing a graph by going as far down one route as possible before backtracking and taking the next route

return addresses

a recursive depth-first traversal automatically implements a stack to hold local variables, parameters and ... each time the subroutine is called

breadth-first traversal

the method of traversing a graph by firstly visiting all the neighbours of a node and then all the neighbours of the first node visited and all the neighbours of the second node and so on

queue

a breadth-first traversal is iterative and uses a ... to keep track of nodes that still need to be visited

scheduling jobs

a depth-first search could be used to solve problems like mazes, where it can be represented as a graph, or for ... where certain tasks must be completed before others

web crawlers

a breadth-first search can be used to find the shortest path, for ... and in facebook to represent friends

Dijkstra’s shortest path algorithm

an algorithm with one cost function - the real cost value from the source to a given node and works by finding the shortest path to every node

A* algorithm

a general path-finding algorithm which has two cost functions - the real cost value and the approximate cost from the node to the goal node

goal node

Unlike Dijkstra's algorithm, where the shortest path to every node is found, the A* algorithm has a focus of reaching the ...

GPS navigation systems

Shortest path algorithms are needed for ... and computer networks (such as the internet)