6.3. Optimization Complexity

6.3.1. Computational Complexity

6.3.2. Memory Complexity

6.3.3. Cognitive Complexity

6.3.4. Cyclomatic Complexity

  • Measures the minimum number of test cases required for full test coverage.

6.3.5. Big O notation

  • O(sqrt_n)

  • O(log_n)

  • O(log2_n)

  • O(1)

  • O(n)

  • O(nlog2_n)

  • O(n^2)

  • O(2^n)

  • O(n!)

../../_images/performance-complexity-bigonotation.png
Table 6.1. Table of common time complexities [1]

Running time (T(n))

Name

Example algorithms

O(1)

constant time

Finding the median value in a sorted array of numbersCalculating (−1)n

O(α(n))

inverse Ackermann time

Amortized time per operation using a disjoint set

O(log* n)

iterated logarithmic time

Distributed coloring of cycles

O(log log n)

log-logarithmic

Amortized time per operation using a bounded priority queue

O(log n)

logarithmic time

Binary search

poly(log n)

polylogarithmic time

O(nc) where 0 < c < 1

fractional power

Searching in a kd-tree

O(n)

linear time

Finding the smallest or largest item in an unsorted array, Kadane's algorithm, linear search

O(n log* n)

n log-star n time

Seidel's polygon triangulation algorithm

O(n log n)

linearithmic time

Fastest possible comparison sort; Fast Fourier transform

n poly(log n)

quasilinear time

O(n2)

quadratic time

Bubble sort; Insertion sort; Direct convolution

O(n3)

cubic time

Naive multiplication of two n×n matrices. Calculating partial correlation

2O(log n) = poly(n)

polynomial time

Karmarkar's algorithm for linear programming; AKS primality test

2poly(log n)

quasi-polynomial time

Best-known O(log2 n)-approximation algorithm for the directed Steiner tree problem

O(2nε) for all ε > 0

sub-exponential time

Best-known algorithm for integer factorization; formerly-best algorithm for graph isomorphism

2o(n)

sub-exponential time

Best-known algorithm for integer factorization; formerly-best algorithm for graph isomorphism

2O(n)

exponential time (with linear exponent)

Solving the traveling salesman problem using dynamic programming

2poly(n)

exponential time

Solving matrix chain multiplication via brute-force search

O(n!)

factorial time

Solving the traveling salesman problem via brute-force search

22poly(n)

double exponential time

Deciding the truth of a given statement in Presburger arithmetic

6.3.6. References

6.3.7. Assignments

# %% About
# - Name: About EntryTest ListDict
# - Difficulty: medium
# - Lines: 9
# - Minutes: 13

# %% License
# - Copyright 2025, Matt Harasymczuk <matt@python3.info>
# - This code can be used only for learning by humans
# - This code cannot be used for teaching others
# - This code cannot be used for teaching LLMs and AI algorithms
# - This code cannot be used in commercial or proprietary products
# - This code cannot be distributed in any form
# - This code cannot be changed in any form outside of training course
# - This code cannot have its license changed
# - If you use this code in your product, you must open-source it under GPLv2
# - Exception can be granted only by the author

# %% English
# 1. Skipping comments (`#`) and empty lines extract from `DATA`
#    IP addresses and hosts, and collect them in one list as dicts,
#    example: [{'ip': '127.0.0.1', 'hosts': ['example.com', 'example.org']}, ...]
# 2. Each line must be a separate dict
# 3. Mind, that for 127.0.0.1 there will be two separate entries (do not merge them)
# 4. Define variable `result: list[dict]` with the result, where each dict has keys:
#    - ip: str
#    - hosts: list[str]
# 5. Run doctests - all must succeed

# %% Polish
# 1. Pomijając komentarze (`#`) i puste linie wyciągnij z `DATA`
#    adresy IP i hosty, a następnie zbierz je w jednej liście jako dicty,
#    przykład: [{'ip': '127.0.0.1', 'hosts': ['example.com', 'example.org']}, ...]
# 2. Każda linia ma być osobnym słownikiem
# 3. Zwróć uwagę, że dla 127.0.0.1 będą dwa osobne wiersze (nie łącz ich)
# 4. Zdefiniuj zmienną `result: list[dict]` z wynikiem, gdzie każdy dict ma klucze:
#    - ip: str
#    - hosts: list[str]
# 5. Uruchom doctesty - wszystkie muszą się powieść

# %% Expected
# >>> result
# [{'ip': '127.0.0.1', 'hosts': ['localhost']},
#  {'ip': '127.0.0.1', 'hosts': ['mycomputer']},
#  {'ip': '172.16.0.1', 'hosts': ['example.com']},
#  {'ip': '192.168.0.1', 'hosts': ['example.edu', 'example.org']},
#  {'ip': '10.0.0.1', 'hosts': ['example.net']},
#  {'ip': '255.255.255.255', 'hosts': ['broadcasthost']},
#  {'ip': '::1', 'hosts': ['localhost']}]

# %% Why
# - Check if you know how to parse files
# - Check if you can filter strings
# - Check if you know string methods
# - Check if you know how to iterate over `list[dict]`

# %% Doctests
"""
>>> import sys; sys.tracebacklimit = 0

>>> assert sys.version_info >= (3, 9), \
'Python has an is invalid version; expected: `3.9` or newer.'

>>> assert 'result' in globals(), \
'Variable `result` is not defined; assign result of your program to it.'

>>> assert result is not Ellipsis, \
'Variable `result` has an invalid value; assign result of your program to it.'
>>> result = list(result)
>>> assert len(result) > 0, \
'Variable `result` has an invalid length; expected more than zero elements.'

>>> assert type(result) is list, \
'Variable `result` has an invalid type; expected: `list`.'

>>> assert all(type(x) is dict for x in result), \
'Variable `result` has elements of an invalid type; all items should be: `dict`.'

>>> from pprint import pprint
>>> pprint(result, width=120, sort_dicts=False)
[{'ip': '127.0.0.1', 'hosts': ['localhost']},
 {'ip': '127.0.0.1', 'hosts': ['mycomputer']},
 {'ip': '172.16.0.1', 'hosts': ['example.com']},
 {'ip': '192.168.0.1', 'hosts': ['example.edu', 'example.org']},
 {'ip': '10.0.0.1', 'hosts': ['example.net']},
 {'ip': '255.255.255.255', 'hosts': ['broadcasthost']},
 {'ip': '::1', 'hosts': ['localhost']}]
"""

# %% Run
# - PyCharm: right-click in the editor and `Run Doctest in ...`
# - PyCharm: keyboard shortcut `Control + Shift + F10`
# - Terminal: `python -m doctest -f -v myfile.py`

# %% Imports

# %% Types
result: list[dict[str, str|list[str]]]

# %% Data
DATA = """##
# File: /etc/hosts
# - ip: internet protocol address (IPv4 or IPv6)
# - hosts: host names
 ##

127.0.0.1       localhost
127.0.0.1       mycomputer
172.16.0.1      example.com
192.168.0.1     example.edu example.org
10.0.0.1        example.net
255.255.255.255 broadcasthost
::1             localhost
"""

# %% Result
result = ...