Search algorithms

Question 1

linear search algorithm

Answer 1

traverse the list using a for loop

compare each item to the search term

if there is no match it is not in the list

Question 2

big - O complexity of the linear search

Answer 2

O(n)

num operations directly proportional to num items in the list

Question 3

returned value of linear search function

Answer 3

boolean - True or False

Question 4

linear search benefits and limitations

Answer 4

linear search can be used on any list, but takes more operations than binary search

Question 5

binary search

Answer 5

find midpoint

compare to search term

discard half of the list where the search term is not found

repeat until found or list is down to one item

Question 6

Big- O complexity of binary search

Answer 6

O(log n)

Question 7

two ways of implementing binary search

Answer 7

• slicing list into smaller list
• using “start” and “stop” markers to mark the ara of the list where the search term might occur

Question 8

benefits and limitations of binary search

Answer 8

• faster than linear search
• can only be used with an ordered list

Question 9

five levels of big O complexity in order

Answer 9

constant - O(1)
logarithmic - O(log n)
linear - O(n)
polynomial- O(n^x)
exponential - O(x^n)

Question 10

how to define the complexity of an algorithm

Answer 10

constant - no loop
logarithmic- dividing a list in half repeatedly
linear - a for loop
polynomial - a loop inside a loop
exponential - an even more complex program

Question 11

how to determine the complexity of an expression

Answer 11

Ignore the actual numbers

Look for any places where n occurs in the expression

Compare this to the big-O levels to find a match to the shape

If there is more than one example, take the most complex

Question 12

two ways to swap values

Answer 12

tuple substitution

three- line swap using a “temp” variable

Question 13

bubble sort

Answer 13

traverse list
compare each value to the next, swap if wrong way around
traverse multiple times until there are no swaps

Question 14

how to recognise bubble sort

Answer 14

a for loop inside a while loop

Question 15

big- O complexity of bubble sort

Answer 15

polynomial
O(n^x)

Question 16

evaluate bubble sort

Answer 16

very slow
avoid using unless list is short

Question 17

insertion sort

Answer 17

traverse list once
compare value at marker to one before it
if smaller, pass all the way back and insert it in its correct position

Question 18

how to recognise insertion sort

Answer 18

for loop with a backwards for loop inside it

Question 19

big O complexity of insertion sort

Answer 19

polynomial
O(n^x)

Question 20

evaluate insertion sort

Answer 20

usually faster than bubble sort

works well to tidy up list which is almost sorted

Question 21

merge sort

Answer 21

split list into many small lists of one

marge to make sorted lists of two

continue to merge until one sorted list

Question 22

how to recognise merge sort

Answer 22

two functions -
one to split the list
plus a merge function

Question 23

merge sort complexity

Answer 23

O ( n x logn )

Question 24

evaluate merge sort

Answer 24

fast and reliable

takes up more space in memory than other sorts

Question 25

quick sort

Answer 25

find a pivot value

sort list into two partitions of values larger and smaller than the pivot

repeat recursively on each of the partitions

Question 26

recognise quick sort

Answer 26

partition function
called by a sort function

Question 27

quick sort complexity

Answer 27

polynomial
O(n^x)

usually much faster

Question 28

evaluate quick sort

Answer 28

fast, almost as fast as merge sort

not as reliable as merge sort

does not take up extra space in memory