Searching & sorting

What is linear search?

Starts at one end of the list and checks each element until either the target is found or the list ends

What is linear search best for?

Best for "small" lists (less than 50 elements)

What is the best case (efficiency) for linear search?

O(1)

What is the average case (efficiency) for linear search?

O(n) - average of n/2 comparisons for a list of n elements

What is the worse case (efficiency) for linear search?

Worst case: O(n)

Give a generic code for linear search

What is the condition for binary search?

Only works on sorted lists

How does binary search work?

Divides the search interval in half repeatedly divide & conquer:

• It determines which half of the list contains the search term.

• It recursively checks that half and stops if item found or list empty.

What is the best case (efficiency) for binary search?

O(1)

What is the average case (efficiency) for binary search?

O(log n) - divides the interval by 2 each time: log₂n

What is the worst case (efficiency) for binary search?

O(log n)

Compare the efficiency between the linear search and binary search and when you wanna use which one

• Binary search is faster than linear search, but only works on sorted lists.

• Searching an unsorted list with linear sort is still faster than first sorting a list and then using binary search though

Which searching does dictionary used and what is the efficiency of it?

Python dictionaries use 'hash table' searching, which is always O(1)

What is selection sort?

Selects the smallest item in the list and swaps it with the first item, then repeats for the rest of the list until fully processed.

What is the space complexity of selection sort

Sorts "in place" - doesn't create a new list: Space complexity O(1).

What are the 3 cases (best, average and worse) for selection sort (time complexity)

What is merge sort?

Divides the list into n sublists and repeatedly merges them producing sorted sublists until one sorted sublist remains

What should you do when drawing a merge sort tree?

When drawing the merge sort tree, show all individual splits and merges

What is the space complexity of the merge sort?

Not "in place" – creates a new list: Space complexity O(n).

What are the 3 cases (best, average and worse) for merge sort (time complexity)

Who proposed the merge sort?

Proposed by von Neumann in 1945

Give a generic code for selection sort

Give a generic code for merge sort

Give a generic code for quick sort

What is quick sort

Partitions the list based on a pivot value, then sorts each partition recursively

What is the space complexity of the quick sort

"in place" sort: Space complexity O(1)

What are the 3 cases (best, average and worse) for quick sort (time complexity)

What is a Big-O notation?

An upper bound estimate on algorithm efficiency → it compares how the algorithm responds to changes in input size

Is Big O notation exact?

Nope

How do you simplify the Big O notation

What are the common time complexity

What do we mean by a stable sort?

A "stable sort" is one where the relative positions of items with the same key do not change

What can the efficicy class tell you about the in

Compare the advantages of each sorting algorithm

Give generic code for binary search

Give generic code for linear search

Give generic code for selection sort