Big O notation in mathematics and computer science

What’s Big O notation?

Way of comparing rates of growth of different functions, which depending on function argument size. It is often used to compare the efficiency of different algorithms, which is done by calculating how much memory is needed (space complexity), and how much time it takes to complete (time complexity).
— SE Wikipedia

Consistent and concise way to analyze the efficiency of algorithms is a Big O notation. It gives answer to questions like this: If there are $N$ data elements (sometimes need to determine), how many steps and resources will the algorithm X take to do something? How to compare any two algorithms efficiency? Is this fast or slow algorithm as fast as algorithms generally go?

Big O key concepts:

Growth is with respect of input
Constants and lower order terms are ignored
Worst case is usually the way we measure

Key question which describe Big $O$ ?
If there are N data elements, how many steps will the algorithm take?

Big O is about how will an algorithm’s performance (efficiency) change as the data increases?

Big O Notation categories, linear growing, quadratic growing, exponential grow, etc.:

Big O notation

Big O Notation allows us to easily categorize the efficiency of a given algorithm, which focus on the number of operations an algorithm requires to complete.

An algorithm that is $O (N)$ is also known as having linear time.

If there are $N$ data elements, how many steps will linear search take?
$N$ steps, $O (N)$

$O (1)$ algorithm can also be referred to as having constant time. At it always faster than $O (N)$ , even if $O (1)$ takes a lot of steps, googolplex steps for example, at some input data size it’s become faster.

Big O Notation resolves the key question: if there are $N$ data elements, how many steps will the algorithm take?

Big O is not only about how many steps an algorithm takes with specific input, but more about how the number of steps grows as the size of the input grows. So it’s describe relationship between input data and the algorithm efficiency.

Let’s say we have an algorithm that always takes three steps no matter how much data there is. That is, for N elements, the algorithm always takes three steps. How would you express that in terms of Big O?
The algorithm is $O (1)$ . Because the number of steps is constant. Even if algorithms taking a lot of steps, at some point it will be faster than $O N)$ .

Let’s say you have $N^{2} + 2 N - 2$ steps in your algorithm, how to express that with Big O?
At first glance you can simplify this to $O (N^{2} + N)$ , but Big O Notation only takes into account the highest order of N when we have multiple orders added together and we reducing it to $O (N^{2})$ .

Is $O (N)$ more efficient than $O (1)$ ?
$O (N)$ is less efficient than $O (1)$ , no matter how many steps (N) the $O (1)$ algorithm always takes 1 step or constant number. Even if $O (1)$ takes a lot steps at some point it well be more efficient.

Big O can describe the best and worst case scenario of an algorithm. But Big O Notation generally refers to the worst case (pessimistic approach) scenario, unless specified otherwise.

$O (l o g_{2} N)$ is the Big O way of describing an algorithm that increases one step each time the data is doubled.

$O (l o g N)$ means that for $N$ data elements, the algorithm would take == $lo g_{2} N$ (omitting 2)== steps.

$O (l o g N)$ means the algorithm takes as many steps as it takes to keep halving the data elements until we remain with 1.

If there are 8 elements, the $O (l o g N)$ algorithm would take 3 steps.

Bubble sort taking about $N^{2}$ steps, selection sort about $N^{2} /2$ steps, what is complexity of these algorithms?
$O (N^{2})$ , yes it’s correct, there major rule of Big O: Big O notation ignores constants. Big O Notation never includes regular numbers that aren’t an exponent (except for $O (1)$ ).

Which Big O notation need to use in these cases?

$N^{2} /2$
$N /2$
$N^{2} + 10$
$2 N$
$100 N$
$O (N^{2})$
$O (N)$
$O (N^{2})$
$O (N)$
$O (N)$

Is this algorithm $O (N)$ or $O (l o g N)$ ?

def is_prime(number):
    """Check number is prime (only 2 factors: 1 and themselves)"""
    for i in range(2, number):
        if number % i == 0:
            # we found a factor when we able to divide number with it
            print(f"NOT prime: Found factor {i} for number {number}")
            return False
 
    print(f"prime: Number {number} is prime")
    return True
 
is_prime(59)
is_prime(60)
is_prime(61)
is_prime(66)
is_prime(67)

Results:

prime: Number 59 is prime
NOT prime: Found factor 2 for number 60
prime: Number 61 is prime
NOT prime: Found factor 2 for number 66
prime: Number 67 is prime

It’s $O (N)$ . When passing the number N, how many steps will the algorithm take, for 7 is 5, for 101 about 101, etc. So it’s taking linear time, we generate $N$ steps depending on number.

Example of where two algorithms can be expressed the same way using Big O Notation, but further analysis is needed to figure out which algorithm is faster.

def print_even_numbers_v1(upper_bound):
    number = 2
 
    while number <= upper_bound:
        if number % 2 == 0:
            print(number)
        number += 1
 
def print_even_numbers_v2(upper_bound):
    number = 2
 
    while number <= upper_bound:
        print(number) # 2, ...
        number += 2   # skip next number 3 and we print 4

What’s complexity of two algorithms, how many significant steps has first version? Is second version faster?
Complexity of both algorithms is $O (N)$ . Significant steps for first version: $N$ comparisons, $N /2$ printing and $N$ incrementing, in total $2.5 N$ steps (practically can be more). Yes second version is much faster, about $N /2$ steps, we skip half of comparisons and half of iterations and half of incrementing. TODO: need verify.

What’s complexity of this algorithm?

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
    }
}

If it doesn’t get optimized out by the compiler, the complexity will still be $O (n^{2})$ - even though the loops bodies are empty, the condition checks and implementation of both counters are still valid operations which have to be performed.

Inom Turdikulov

Big O notation in mathematics and computer science

To-do

Graph View

Backlinks

Table of Contents