Search algorithms

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

O(n) num operations directly proportional to num items in the list

boolean - True or False

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

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

O(log n)

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

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

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

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

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

tuple substitution three- line swap using a “temp” variable

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

a for loop inside a while loop

polynomial O(n^x)

very slow avoid using unless list is short

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

for loop with a backwards for loop inside it

polynomial O(n^x)

usually faster than bubble sort works well to tidy up list which is almost sorted

split list into many small lists of one marge to make sorted lists of two continue to merge until one sorted list

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

O ( n x logn )

fast and reliable takes up more space in memory than other sorts