Looking from the outside, Big O is very scary. Why? O is not an abbreviation for a word, it’s a concept. It’s a concept used in mathematics. It’s a concept in computer science when we want to talk about algorithms. What is algorithms? Yeah, that is another scary concept on its own but we’re here to talk about the big O notation.
When we write a program, what is one of the first thing that may come to mind? How fast is it? Yes, that’s right! We want a program to run as fast as possible. The faster it is, the more efficient it is. Big O notation allows us to measure the efficiency of a program.
This notation is known as constant time. The execution time is constant no matter how many times you run it. In terms of scalability, it is a flat line meaning it will take the same amount of time. It is very scalable and predictable.
>>> odd_numbers = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21] >>> def first_value(odd_numbers): ... return odd_numbers ... >>> print(first_value(odd_numbers)) 1
As shown above, no matter how many times you run the code snippet, it will return about the same time. There will be some variation in the time, but for the most point, it will be near a constant value.
With this notation, it means the execution time of your program increases linearly according to the number of inputs as noted by n. The time it takes to run the program increases with the number of items in the array.
>>> odd_numbers = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21] >>> def linear_search(odd_numbers, chosen): ... for index in range(len(odd_numbers)): ... if chosen == odd_numbers[index]: ... return index ... >>> print(linear_search(odd_numbers, 9)) 4
This is linear time because the more items you add in the array, the longer it will take the program to run.
When searching for an item from a list, a logarithmic time complexity can happen as you go through each value in the input data. This is found in a binary search when you are finding the position of an item from a sorted list.
>>> odd_numbers = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21] >>> def binary_search(odd_numbers, value): ... total = len(odd_numbers) ... left = 0 ... right = total - 1 ... while left <= right: ... middle = (left + right) / 2 ... if value < odd_numbers[middle]: ... right = middle - 1 ... elif value > odd_numbers[middle]: ... left = middle + 1 ... else: ... return middle ... >>> print(binary_search(odd_numbers, 13)) 6
Each step of the way, you are finding the middle of the list and repeating it as the number of items in the list gets smaller and smaller. You half the number of items in the list and keep repeating the process until you find the value in the list.