Edexcel Algorithm efficiency

Do Now

Create a list with 3 people in it
add a new person to the end of the list
print the list
remove the last person from the list
replace the 2nd person in the list with "Mario"
print the list
print the list but use [-1] .

Stretch:
keep asking the user if they want to add a new person to the list until they say no. add each person to the list and print the list

​Algorithm Efficiency

:D

Teams > Topic 1 > Algorithm Efficiency

​Time – how long it takes to run (often measured in terms of the number of steps or operations). Space – how much memory it uses during execution.

​Best case: 1 comparison
Worst Case: 100 comparisons

Multiple Choice

State the best case for a linear search algorithm.

• The best case for a linear search algorithm occurs when the target element is the first element in the list.
• The best case occurs when the target element is in the middle of the list.
• The best case occurs when the list is empty.
• The best case occurs when the target element is the last element in the list.

Multiple Choice

State the worst case for a linear search algorithm.

• The worst case occurs when the list is sorted in ascending order.
• The worst case occurs when the target element is at the first position in the list.
• The worst case occurs when the target element is not present or is at the last position in the list.
• The worst case occurs when the list is empty.

Multiple Choice

Explain the best case search for a binary search

• The best case occurs when the target is at the beginning of the array.
• The best case occurs when the target is at the end of the array.
• The best case occurs when the array is empty.
• The best case occurs when the target is at the midpoint of the array.

Multiple Select

In the worst-case scenario for a binary search...
(multiple choiuce

• it takes the maximum number of steps

• the target isn't in the list

• the target it in the middle

• it find the target immediately

Multiple Choice

Describe an in-place algorithm

• An in-place algorithm modifies data directly without using extra space proportional to the input size.
• An in-place algorithm can only be applied to sorted data.
• An in-place algorithm creates a copy of the data before modification.
• An in-place algorithm requires additional memory for processing.

Multiple Choice

Describe an out-of-place algorithm

• An out-of-place algorithm is one that requires additional memory space and does not modify the input data in place.
• An out-of-place algorithm sorts data in a single pass without extra memory.
• An out-of-place algorithm is one that runs in constant space and time.
• An out-of-place algorithm modifies the input data directly.

Open Ended

Explain the effect on efficiency of using a merge sort algorithm instead of a bubble sort algorithm on this list: 9     4     3     5     5     1     7

(2 marks)

​merge will use more memory 1 because it will make copies of the list 1 the bubble will use less memory 1 because it is an in-place 1 sort the merge will take more time to write and debug 1 because it is a more complex algorithm 1 the bubble will probably take less time to write 1 because it is simple / well known 1

Teams - Task 1