Big O Cheatsheet Complexity

Efficiency of stacks, queues, linked lists, doubly linked lists, and more data

structures when inserting, deleting and searching

Big O notation is defined by Wikipedia as a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. It is a member of a family of notations invented by Paul Bachmann,[1] Edmund Landau,[2] and others, collectively called Bachmann–Landau notation or asymptotic notation.

In computer science, big O notation is used to classify algorithms according to how their running time or space requirements grow as the input size grows.[3] In analytic number theory, big O notation is often used to express a bound on the difference between an arithmetical function and a better understood approximation; a famous example of such a difference is the remainder term in the prime number theorem.

Big O notation characterizes functions according to their growth rates: different functions with the same growth rate may be represented using the same O notation.

When you are studying Data Structures and Algorithms is one of the things that you learn and you should not forget.

When I learnt them was useful to have them in an ordered table written in my notebook. So here it comes; a quick cheatsheet to check whenever you might need it.

In the following table you have the name of the Data Structure, and the classification for search, insert, and delete in the Average and the Worst Case.

Data Structure	Search AC	Insert AC	Delete AC	Search WC	Insert WC	Delete WC
Stack	O(n)	O(1)	O(1)	O(n)	O(1)	O(1)
Queue	O(n)	O(1)	O(1)	O(n)	O(1)	O(1)
Sorted Array	O(log n)	O(n)	O(n)	O(log n)	O(n)	O(n)
Linked List	O(n)	O(1)	O(1)	O(n)	O(1)	O(1)
Doubly Linked List	O(n)	O(1)	O(1)	O(n)	O(1)	O(1)
Binary Tree	O(log n)	O(log n)	O(log n)	O(log n)	O(log n)	O(log n)
Binary Search Tree	O(log n)	O(log n)	O(log n)	O(n)	O(n)	O(n)
AVL Tree	O(log n)	O(log n)	O(log n)	O(log n)	O(log n)	O(log n)
Hash table	O(1)	O(1)	O(1)	O(n)	O(n)	O(n)

Here some basic implementations in Python.

Stack

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

from namedlist import namedlist

class Stack():
    __slots__ = ["_values"]

    def __init__(self, iterable=None):
        self._values = []
        if iterable is not None:
            for value in iterable:
                self.push(value)

    def __len__(self):
            return len(self._values)

    def empty(self):
        return len(self._values) == 0

    @property
    def top(self):
        assert not self.empty(), 'No elements'
        return self._values[-1]

    def push(self, value):
        self._values.append(value)

    def pop(self):
        assert not self.empty(), 'No elements'
        return self._values.pop()

    def clear(self):
            self._values.clear()

    def copy(self):
        new_stack = Stack()
        new_stack._values = self._values.copy()
        return new_stack

    def __eq__(self, other):
        return self._values == other._values

    def __repr__(self):
          return ('Stack([' + ', '.join(repr(x) for x  in self._values) + '])' )

Queue

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

from namedlist import namedlist


class Queue():
    _Node = namedlist('Node', 'value next')

    __slots__ = ['_front', '_back']

    def __init__(self, iterable=None):
        self._front = self._back = None
        if iterable is not None:
            for value in iterable:
                self.enqueue(value)


    def is_empty(self):
        return self._front is None


    @property
    def front(self):
        #assert not self.is_empty(), 'Empty queue'
        return self._front.value


    @property
    def back(self):
        assert not self.is_empty(), 'Empty queue'
        return self._back.value


    def clear(self):
        self._front = self._back = None


    def enqueue(self, value):
        new_node = Queue._Node(value, None)
        if self.is_empty():
            self._front = self._back = new_node
        else:
            self._back.next = self._back = new_node


    def dequeue(self):
        assert not self.is_empty(), 'Empty queue'
        value, self._front = self._front
        if self._front is None:
            self._back = None
        return value


    def copy(self):
        new_queue = Queue()
        if not self.is_empty():
            node = self._front
            new_queue._front = back = Queue._Node(node.value, None)
            while node.next is not None:
                node = node.next
                back.next = back = Queue._Node(node.value, None)
            new_queue._back = back
        return new_queue


    def __len__(self):
        n = 0
        node = self._front
        while node is not None:
            node = node.next
            n += 1
        return n


    def __eq__(self, other):
        x = self._front
        y = other._front
        while x.next is not None and y.next is not None:
            if x is None and y is None:
                return True
            x = x.next
            y = y.next


    def __repr__(self):
        values = []
        node = self._front
        while node is not None:
            values.append(node.value)
            node = node.next
        return 'Queue([' + ', '.join(repr(x) for x in values) + '])'

(*) Example implementations in Python written by German Osella Massa for a Data Structures Course and published in : https://github.com/gosella/DS/tree/master/Python