asymptotic notation (big-o), cliffnotes

05 Aug, 2025

big-o (originally an omicron) is a way of analysing the runtime it takes the algorithm to execute as the input size grows.

polinormial

• the common x(y) we have learnt in school can be represented as O(n), where the n is a single variable. Example: sum(nums). it will be longer, because we need to loop through the arguments.
• heapq.heapify(nums) and sliding-window algorithms (optimizing by updating results incrementally rather than recalculating from scratch for each window) runs O(n).

    ^
time|              ●
    |           ●
    |         ●
    |      ●
    |   ●
    |●_____________> input

• O(1) - no matter how much the input size grows, the time is constant. Example: nums.append(5)

     ^
time |                                         
     |                    
     |                    
     | ● ● ● ● ● ●
     |_____________>
               input

-O(n^2). Example: iterating though a 2-dimensional array or iterating though an n-sized array n times.

    ^
time|          ●
    |        ●
    |      ●
    |    ●
    |  ●
    |●_____________> input

• O(logn): log n is usually applied to the binary search. with each iteration, we eliminate half of the components. 2^x = n. xis the number of times we can take the array and divide it by 2. for very large imput sizes, O(logn)is almost the same as O(1). the difference between O(logn) and O(n) is massive.

non-polinormial

• O(2^n)
• O(n!), comes up mostly in permutations

src