# Big-O Notation

# Introduction

Big-O notation is used to estimate time or space complexities of algorithms according to their input size. Big-O notation usually only provides an upper bound on the growth rate of the function, so people can expect the guaranteed performance in the worst case. Due to the reason, Big-O is more widely used by developers compared to Big-Theta and Big-Omega.

# Definition

Let and be two functions defined on some subset of the real numbers.
If there is a positive constant such that for all sufficiently large values of , the absolute value of is at most multiplied by the absolute value of . That is, if and only if there exists a positive real number and a real number such that

for all

Let’s see examples for better understanding. There are two algorithms written in C for sum from 1 to n. (The comment of each line means the operation number.)

```
// Algorithm1
int calcSum(int n) {
int i = 1; // 1
int sum = 0; // 1
for(; i<=n; ++i)
{
sum = sum+i;
} // 3n+1
return sum;
}
// Total operation number: 1+1+3n+1 = 3n+3
```

```
// Algorithm2
int calcSum(int n) {
int count = n; // 1
int sum = 1+n; // 1
sum = sum*count; // 1
sum = sum/2; // 1
return sum;
}
// Total operation number: 1+1+1+1 = 4
```

##### Big-O notation for Algorithm1

There exists and such that
for all
(e.g. )

Therefore,

##### Big-O notation for Algorithm2

There exists such that
(e.g. )

That means,

# Polynomial Expression

In real situations, we may face more complicated expressions than the examples above. Let’s suppose that the complexity function is , and we need to simplify this expression using Big-O notation. To say the conclusion first, among the three terms , , and , the one with the highest growth rate will be used as follows: .

#### Theorem

, where and are real numbers.

**Proof:**

For all ,

Therefore, where and Consequently,

Going back to , we can use the same approach in order to make Big-O notation for .

For all ()

That is, (, )

# Other Useful Theorems

Many algorithms consist of two or more sub-procedures. We can derive their proper Big-O notations using the sub-procedure’s Big-O.

#### Theorem 1

Let and .

Then, .

**Proof:**

By the definition of Big-O, there exists
such that for all and for all .

Also, let , , and .

Corollary:

, where and .

#### Theorem 2

Let and .

Then, .

**Proof:**

Let and

# References

- Big O notation, Wikipedia, https://en.wikipedia.org/wiki/Big_O_notation
- Discrete Mathematics and its Applications 5th edition, Kenneth H. Rosen, McGraw-Hill Education
- Data Structures for Game Programmers, Ron Penton, PremierPress
- Big-O Notation, openparadigm’s blog, http://openparadigm.tistory.com/20