Facebooktwitterredditpinterestlinkedintumblr

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.

O(1)

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[0]
... 
>>> 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.

O(n)

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.

O(log n)

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.

Tim Miller

Tim has always been obsessed with computers his whole life. After working for 25 years in the computer and electronics field, he now enjoys writing about computers to help others. Most of his time is spent in front of his computer or other technology to continue to learn more. He likes to try new things and keep up with the latest industry trends so he can share them with others.

Leave a Comment