Skip to main content
Informatik.uz
Bachelor’s · Year 1Chapter 2. Programming fundamentals

Algorithm complexity (Big-O)

To compare algorithms, we estimate their time and space complexity. We look at Big-O notation, the main complexity classes and how much they differ on large data.

Topic 3 of 32 min readUpdated October 27, 2026
All topics (3 of 3)

Chapter 1. Introduction to information technology

  1. 1Information encoding and the binary system

One problem can be solved by different algorithms, and to compare them the notion of complexity is introduced. Time complexity is the number of elementary operations an algorithm performs as a function of the input size n, and space complexity is the amount of extra memory it uses. Operations are counted rather than seconds, because running time depends on the computer and the programming language.

Big-O notation gives an upper bound on the growth rate of a function. Formally, if there exist a constant c > 0 and a number n0 such that f(n) ≤ c · g(n) for all n ≥ n0, then f(n) = O(g(n)). In practice, constant factors and lower-order terms are dropped: 3n + 5 = O(n), n² + 100n = O(n²). Usually the worst case of an algorithm is estimated.

The most common complexity classes are ordered by growth rate. O(1) is constant (for example, accessing an element a[i]); O(log n) is logarithmic (binary search); O(n) is linear (one loop, for example for x in a: s += x); O(n log n) is efficient sorting (merge sort, Timsort); O(n²) is quadratic (two nested loops, bubble sort); O(2^n) is exponential (going through all subsets of an n-element set). The complexities of consecutive blocks add up and the largest one remains, while the complexities of nested loops multiply.

The difference becomes huge for large n. If a computer performs about 100 million simple operations per second, then for n = 1,000,000 an O(n) algorithm takes about a hundredth of a second, an O(n log n) algorithm about 0.2 seconds, and an O(n²) algorithm about 10,000 seconds, almost 3 hours. So on large data the complexity of an algorithm affects running time more than the speed of the device.

Key takeaways

  • Complexity shows how the number of operations (or the amount of memory) depends on the input size n.
  • Big-O gives an upper bound on the growth order; constant factors and lower-order terms are dropped.
  • The main classes are O(1), O(log n), O(n), O(n log n), O(n²), O(2^n), with growth rate increasing.
  • Complexities of consecutive blocks add up; those of nested loops multiply.
  • For large n the order of complexity matters more than the speed of the device.

Practice tasks

  1. Reduce these expressions to Big-O form: 5n + 20, n² + 3n + 7, 100, n log n + n, 2^n + n³.
  2. Determine and explain the time complexity of three fragments: one loop for i in range(n): s += i; two nested loops, both over range(n); the loop while i < n: i = i * 2 (with i = 1 at the start).
  3. For random lists of length n = 1000, 2000, 4000, 8000 measure the running time of bubble sort and of the built-in sorted() with the time module; record in a table how the time grows and compare it with the theoretical complexity.

Review questions

Test yourself: think first, then reveal the answer.

  1. 1Why are constant factors dropped in Big-O notation?
    For large n the growth order decides, and a constant factor does not change it and depends on the computer.
  2. 2What is the total complexity if two consecutive blocks have complexities O(n) and O(n²)?
    O(n + n²) = O(n²): the largest term remains.
  3. 3Roughly how many times does the number of operations differ between O(n²) and O(n log n) algorithms for n = 1000?
    n² = 1,000,000 and n log2 n ≈ 10,000, so about 100 times.

0 of 3 topics completed

Sign in to mark