3 - Fundamentals of Algorithms Flashcards
What is the complexity of merge sort?
O(nlogn)
What is the complexity of bubble sort?
Explain why this is.
O(n²)
In each pass through the list n items will be examine. There will be at most n passes through the list.
What is the complexity of binary search?
Explain why this is.
O(logn)
Each comparison halves the size of the list that has to be searched through.
What is the complexity of linear search?
Explain why this is.
O(n)
As the size of the list increases the time taken increases at the same rate.
What is the complexity of binary-tree search?
O(logn)
What are the steps for Breadth-First Search?
- Mark all vertices as unvisited
- Choose a starting vertex
- Visit the starting vertex and mark it as visited
- Enqueue starting vertex in the queue
- Dequeue a vertex from the queue
- For each neighbouring vertex of this vertex, if it is univisited visit it, mark it as visited and enqueue it in the queue
- Repeat the processor of dequeuing vertices and visiting its neighbours until the queue is empty
What are the steps for Depth-First Search using a stack?
- Mark the starting vertex as discovered
- Push the starting node onto the stack
- Pop the top vertex off the stack and mark and visit it
- Push each of this vertex’s neighbours to the stack and mark them as discovered
- Repeat the processes of popping vertices and pushing their neighbours to the stack until the stack is empty
What is a common use of Breadth-First Search?
To find the path containing the least number of nodes between two points in an unweighted graph.
What is a common use of Depth-First Search?
It is commonly used to navigate a maze.
What are the steps for linear search?
- Start with the beginning of the list
- Compare each item with the item you’re searching for
- Stop either when the item is found or the end of the list is reached
What are the steps for binary search?
- For a sorted list
- Set the front pointer to 0 and the rear pointer to the index of the last item in the list
- Compare the item in the middle of the two pointers with the item you’re looking for
- If the items are the same, the item is in the list
- If the middle item is less than the item to search for, change the rear pointer to the middle - 1
- If the middle item is greater than the item to search for, change the front pointer to the middle + 1
- Repeat the processes of comparing the middle item until either the item is found or the front pointer is greater than the rear pointer
What are the steps for binary tree search?
- Start at the root
- Compare the item at the root to the value you’re searching for
- If it is the same, the item has been found
- If the root is higher, check the left child
- If the root is lower, check the right child
- Keep comparing the value to different nodes until either the item is found or the item has been compared with a leaf node
What are the steps for bubble sort?
- Compare the first item to the second item and swap them if they are in the wrong order
- Compare the second item with the third item and swap them if they are in the wrong order
- Keep comparing each pair of adjacent items and swapping them if they are in the wrong order
- After each pair of cards have been compared the first pass is complete
- For the next pass the item at the rear of the list doesn’t need to be compared with (as it is already in the correct position)
- For each pass, the number of items at the rear of the list that don’t need to be compared with increases by 1
- Stop when there is only 1 item that hasn’t been discounted from the comparisons
What are the steps for merge sort?
- Repeatedly split the list in half until each sublist contains only 1 item
- Merge each sublist with the sublist that it was most recently split from so that the new list they form is ordered
- Continue merging the sublists until they form a single list
What approach to problem solving is merge sort an example of?
‘Divide and conquer’
