Computer Science for STEM: The PreTeXt Interactive Edition

A major part of computer science is studying algorithms. There are two types of algorithms that are spoken about very often: search and sort. Not only are they great for learning about Big O and algorithms, but they’re very applicable in the real world.

As the internet grows and the data we store grows, companies have to wrestle with the large amounts of data they have. Imagine if you’re Google and you’re looking for one user out of one billion. Now imagine you need to do that a thousand times a minute, with people doing it at the same time. The code you write and the algorithms you use become massively important to how quickly these operations can be done.

Linear search is the most basic searching algorithm, and the most intuitive. Quite simply, you look through whatever you’re considering in a linear order; from first to last. This could be a stack of papers, or it could be a list in Python.

# a program which finds 10 in my list, linearly
my_list = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
for element in my_list:
    if element == 10:
        print('found 10!')
        break

Linear search has a best case complexity of O(1), average case of O(n), and worst case of O(n). In the best case, the element we’re looking for is the first element. But in the average and worst cases, we will have to look through some n elements.

Binary search is an improvement upon linear search. Binary search splits the searched list in half and looks at the middle value. If the number we’re searching for is less than that value, we know it must be in the left half of the list; if it’s greater, we know it must be in the right half of the list, and we can repeat this process on smaller portions of the list until we find the number.

Binary search has a best case complexity of O(1), average case of O(logn), and worst case of O(logn).

However, there’s a catch: for binary search to work, the list must be sorted! This is where sorting algorithms can come in. Sorting will not be covered in this class, but we will describe one sorting algorithm for those that are curious.

Selection sort is a simple sorting algorithm. The idea is that we take the smallest element and swap it with the leftmost element, and then the leftmost element becomes the sorted list. We repeat this process, and the sorted portion of the list grows in size each time, so we’re only adding elements from the nonsorted portion of the list to the end of the sorted part of the list.

The time complexity of selection sort is O(n^2) in every case.

Some other common sorting algorithms include Bubble Sort and Insertion Sort, but we will leave those for another class.