Big-O Practical Tips

Nested Call Question

We are analyzing the method "foo". It has no visible iteration. It just calls the method/task "linearSearch" which has O(n).

What is the Big-O of the method "foo"?

Answer: O(n)

We have to include "nested" (sub) tasks in our analysis. Otherwise, it would be like "hiding" steps from the analysis.

foo(anElem) {
	return this.linearSearch(anElem);
}

Adding Terms Question

This algorithm has two O(1) operations (highlighted) and one O(n) operation (the loop).

What is the Big-O level for the algorithm?

Answer: O(n)

The smaller terms "wash away". An explanation follows.

linearSearch(anElem) {
	//Return matching element
	//or null if no match
	let i = 0
	while (i < this.size()) {
		let nextElem = this.get(i)
		if (nextElem.equals(anElem))
			return nextElem
		i++
	}
	return null
}

Explanation for Adding Terms

For the algo shown above, we would start off with this analysis:

 O(n) + O(1) + O(1)

We would recall our discussion about levels highlighting that Big-O terms are wide-band (broad) categories. Therefore, smaller terms "wash away" leaving us with:

 O(n)

Generally we do not need to add Big-O terms. Just use the most dominant term (largest growth rate). E.g. O(n) performs poorer than O(1). Thus O(n) governs.

A math angle if interested...

The wiki gives a nice explanation...

Multiplying Terms Question

What is the Big-O level for this algorithm that calls two tasks each with O(n)?

Answer: O(n)

An explanation follows.

foo(anElem) {
	this.linearSearch(anElem);
	this.linearSearch(anElem);
}

Explanation for Multiplying Terms

For the algo shown above, we would start off with this analysis:

O(n) + O(n)
= 2 * O(n)

Remember, we are only concerned with the effect structure size growth has on the algo. Thus any factor (like "2" here) that is not effected by growth may be eliminated.

2 * O(n)
= O(n)

Wiki does a nice job explaining this...

Question

If we have two algorithms with one being O(1) and the other being O(n), can we conclude that O(1) will always be faster?

No, remember Big-O notation only indicates how an algorithm is affected by structure growth.

We may have an algorithm that does not depend on structure size so is O(1). However, it may be "slow" for other reasons.

Explanation by Example

What is an example where O(n) would likely be slower than O(1)?

In some cases user interface (UI) operations can be quite inefficient.

Here is a case where algorithm #1 "O(1)" would likely be slower than algorithm #2 "O(n)" even though it has a better Big-O level

Given data structure "structure"

Algorithm #1: O(1)
Do a complex user interface (UI) operation that does not depend on structure size.
Assume UI takes about one minute to complete

Algorithm #2: O(n)
Do Linear Search of "structure"