Hello Blog!

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


Share this: