Big O - A Little Math

Quick Index

O(n)
O(n²)
O(log n)
Adding Terms

The number of method operations we do is linearly related to the data. If we do Z operations for collection size 1, then we would do Z*100 for collection size 100.

The number of method operations we do is quadratically (n²) related to the data. If we do Z operations for collection size 1, then we would do Z*100*100 for collection size 100.

The number of method operations grows logarithmically. If we do Z operations for collection size 1, then, using base 2, we would do (Z*log 256) for collection size 256.

Example

Big O does not use measurements. We will use numbers here only for understanding.

We see in the example we have a loop, but we also have the two operations highlighted. So should the Big O be:

 O(n) + O(1)

Remember O(1) is a constant relatively small number and O(n) is a very (very) large number. Let us use a quadrillion for n, and (2) for the constant.

1000000000000000 + 2

The constant (2) is not significant (it is washed away).

public int demo_n(int[] aStructure)  {
	int sum;
	sum = 0;
	for (int eachNumber: aStructure) {
		sum += eachNumber;
	}
	return sum;
}

Data Structures And Algorithms (DSA) (Chapter 105 - Introduction to Algorithm Time Complexity Analysis Using Big-O)

Chapter 105 - Introduction to Algorithm Time Complexity Analysis Using Big-O Big O - A Little Math > CHAP101

Index Intro Concepts Notations Tips Analysis-Types Summary Space Refs

Chapter Top Search Site Contents