Notations

Here is an algorithm we recently looked at.

What is the Big-O for the algo shown?

Answer: O(1)

The effort of this simple algorithm is unchanged as the structure grows in size.

Just for fun: O(1) math...

first() {
	//Return first element
	//Return null for empty case
	if (this.isEmpty())
		return null
	return this.get(0)
}

Method 'last' (DynamicArray)

Here is another algorithm.

What is the Big-O for the algo shown?

Answer: O(1)

The effort of this algorithm is also unchanged as the structure grows in size.

last() {
	//Return last element
	//Return null for empty case
	if (this.isEmpty())
		return null
	return this.get(this.size() - 1)
}

Linear Search

Here is an algorithm we recently looked at.

What is the Big-O for the algo shown?

Answer: O(n)

This algorithm will iterate (loop) more times (i.e. "work harder) as structure size grows.

And the "work" increases linearly relative to structure size "n".

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
}

Sum Every Third Integer

Assume we have a dynamic array of integers here.

We are iterating on less elements (every third element).

What is the Big-O for the algo shown?

Answer: O(n)

This algorithm will also iterate (loop) more times (i.e. "work harder) as structure size grows.

And the algorithm "work" also increases linearly with structure size growth.

The effort (iterating on every third) is less than the "linear search" example (iterating on every element) -- but remember we are categorizing broadly.

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

Example

A variation of O(n) here. We have a nested loop (a loop in a loop). Hopefully much rarer in our algorithms.

This is called O(n²).

A little math...

nestedLoopSum() {
	//Compute sums in a nested loop
	let i = 0
	let sum = 0
	while (i < this.size()) {
		let j = 0
		while (j < this.size()) {
			let nextElem = this.get(i)
			sum += nextElem
			j++
		}
		i++
	}
	return sum
}

Example

Again we assume we have collection of integers.

Our iteration count will be logarithmically related to the structure size n.

Here we start var i at (n-1) and find the next i by dividing by 2 for each loop, and end when i equals 0 (somewhat similar to a binary search approach).

This is called O(log n).

A little math...

crazyLogSum() {
	//Compute sums during a logarithmic effort
	let i = this.size() - 1
	let sum = 0
	while (i > 0) {
		let nextElem = this.get(i)
		sum += nextElem
		i = i / 2
	}
	return sum
}

log n vs n

Just for fun.

As shown here, log n is much smaller than n.

log n has only 50 operations for a structure size of one quadrillion.

n = 1000000000000000
//log base 2
log(n) = 50

Example

This is a rarer case where we have a O(log n) operation nested inside an outer O(n) operation.

This is called O(n log n).

Outer loop at O(n)
	Inner operation at O(log n)