Programming: Time Complexity

References

wikipedia**	https://en.wikipedia.org/wiki/Time_complexity
overview	https://medium.com/swlh/a-gentle-explanation-of-logarithmic-time-complexity-79842728a702
tutorial	https://thatcomputerscientist.com/big-o-notation-explained-as-easily-as-possible

Intro

This is also known as Big O Notation.

To find time complexity:

• find the fastest growing term
• take out the coefficient

Time complexity favours the worst possible outcome.

For example

def find_item(num, items):
    for i in range(10):      # O(1)
        if items[i] == num:  # O(n)
            return i         # O(1)
    raise IndexError()       # O(1)

# longest is O(n), so that is complexity

Common Complexities

These are some of the most common time complexities, but all kinds of variants exist.

For example:

sort list                           # O(n)
find item in list, by halving list  # O(log(n))
# O(n log(n))

See https://en.wikipedia.org/wiki/Time_complexity for more.

constant O(1)

# T = a + c
#
#    a = time to run function
#    c = (coefficient) time to invoke python, call function, etc.


def do_nothing(nums):
    return nums

do_nothing([1, 2, 3])

logarithmic O(log n)

A logarithm is the opposite of an exponent (it is used to solve for an exponent).

For example:

log(2)8   # what power of 2 makes 8?
2^3 == 8  # the logarithm(2) of 8 is 3

# we are halving the results each time
8 -> 4 -> 2 -> 1

log(10)100   # what power of 10 makes 100?
10^2 == 100  # the logarithm(10) of 100 is 2

# we are tenthing the results each time
100 -> 10 -> 1

A logarithmic time complexity then is one that discards results as it works. Bubble-sorting is an example of a log(2) time complexity.

items = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
def find_number(num, items):
    """ Finds a list-item within a list - halving results each time.
    """
    items = sorted(items)
    index_low = items[0]
    index_high = items[-1]

    while True:
        test_index = (index_high - index_low) / 2
        test_val = items[test_index]

        if test_val == num:
            return test_index

        if test_val < num:
            index_low = test_index
        else:
            index_high = test_index

        if index_high == index_low:
            raise IndexError('provided `items` does not contain number: {}'.format(num))

linear O(n)

# T = an + c
#
#   T = time to run
#   n = number of elements in array
#   a = time it takes to run function once
#   c = (co-efficient) time it takes to invoke function, invoke interpreter, etc

for i in range(n):
    a()

exponential O(n^2)

# T = a(n^2) + bn + c
#
#   T = time to run
#   n = number of elements in array
#   a = time it takes to run function once
#   b = 
#   c = (co-efficient) time it takes to invoke function, invoke interpreter, etc

for i in range(n):
    for ii in range(n):
        a()