2.3.1 Algorithms Flashcards
(17 cards)
Describe what is meant by Best time O(n) complexity [3]
- Linear.
- Best time grows at the same rate as the number of elements.
- This is the case when the data is already in order.
Describe what is meant by Average and worst time O(n²) complexity [3]
- Polynomial / Quadratic
- Worst and average time is proportional to the square (polynomial) of the number of elements
- Worst case is when the data is initially in the reverse order
Describe what is meant by Worst Space O(1) complexity [3]
- Constant
- Will always take the same amount of memory (in addition to the list itself)
- Binary Tree / Binary Search Tree
The contents of “processedData” are shown: 0|0.5|0|1|2|1.5|1
The data needs to be sorted into ascending order.
Explain how a bubble sort algorithm sorts data. Use the current contents of “processedData” in your explanation [5]
- Compares each pair of data e.g. 0 and 0.5
- If they are in the correct order it moves to the next pair e.g. 0.5
and 0 - If they are in the wrong order it swaps them e.g. 0.5 and 0
becomes 0 and 0.5 - Continues to the end of the array e.g. Pass 1 complete
- If there has been a swap it checks again e.g. Pass 2 complete
- If there have been no swaps it is sorted
Explain why a quicksort is known as a divide and conquer algorithm [2]
Because it decomposes data sets into smaller subsets [1 mark]
• ..and then sorts each split subset [l mark]
A one dimensional array holds data that needs to be sorted.
Describe how a quicksort would sort data into ascending order [5]
• Choose a pivot // identify start and end pointers
• Compare each element to the pivot… Il compare start and end pointers
• Put items < pivot in the left sublist
• Put items > pivot in the right sublist
• Choose a pivot in each sublist
• If start pointer is larger than end pointer…
• …then swap data items around
• And repeat the process until each item becomes a pivot
What is the precondition for a binary search?
The data must be in order
Describe how a linear search works [5]
• Compare the search item with the first value
• ….then compare the search item with the next value
• ….repeat the above process until either
• ….the end of the array has been reached or
• ….the search item is found and then stop
• ….then return the array position
An array is shown here:
2|12|1|9|3|5|15|7
Show how a merge sort will sort this section of the array numberArray into ascending numerical order. [4]
- A split the data into individual items [2][12][1][9][3][5][15][7]
- Combine into pairs which are in the right order:
[2|12][1|9][3|5][15|7] - Merge the pairs so that they are in the right order:
[1|2|9|12][3|5|7|15] - Merge for final result:
1|2|3|5|7|9|12|15
How does an insertion sort work? [3]
- Compare the current item being sorted (starting from the first item), to each previous item
- If it is smaller than the previous item then the previous item is moved to the right and the current item takes its place
- If the current item is larger than the previous item then it is in the correct position and the next current item is then sorted
How does a binary search work? [3]
- It compares the middle item to the searched for target item. If the values match then the index is returned.
- If not then the list is adjusted such that:
the top half is ignored if the target item is less than the middle value
or the bottom half is ignored if the target item is larger than the middle value - Once the list has been adjusted, the search continues until the item is found or the item is not in the list
What is the worst-case, best-case and average time complexity for a binary search? [3]
Worst case: O(1)
Best case: O(1)
Average time: O(log(n))
What is the worst-case, best-case and average time complexity for a linear search? [3]
Worst case: O(1)
Best case: O(1)
Average time: O(n)
What is meant by O(2^n)? [1]
An algorithm that takes double the time to execute for each additional data input value.
What is meant by O(log(n))? [1]
An algorithm that takes very little time as the size of the input grows larger
How do breadth first and depth first traversals work? [4]
Breadth first visits the root node then visits all the nodes on the level below from left to right, before doing the same on the next level until all nodes are visited.
Depth first traverses as far down the left most subtree, then visit the right subtree, then visit the root node.
Explain how backtracking is used in a depth-first traversal?
- Depth first starts at the root
- and goes all the way down one branch to the bottom
- When it cannot go any further
- It then backtracks to the previous node
- And continues to backtrack until a node is reached with unvisited children.
- and checks down that branch
