Concepts

Quick Index

Lingo
What is Big-O Notation?
Algorithm Work Effort -- Examples and Quick Quiz
Number of Operations
Big-O Levels and T-Shirts

Common Lingo:

growth -- a structure is growing in size (number of elements) towards infinity
work (effort) -- how hard an algorithm works

Interchangeable Terms:

algorithm / algo
size / structure size / number of elements
growth / grow / grows
work (effort) / effort
iteration / loops / recursion
structure / data structure
ops / operations

What is Big-O Notation?

Assume we have:

A given data structure (a dynamic array, linked list, etc)
An algorithm that operates on the structure

Big-O analysis basically consists of two steps:

Envision the structure growing in size (towards infinity)
Determine the effect that this growth has on algorithm work (effort)

We then use Big-O notation to classify the change in "work" (relative to growth)

Examples will help.

Algorithm Work Effort -- Examples and Quick Quiz

Available Context for Examples

In the following examples, assume we are adding methods (algorithms) to a dynamic array.

Our context (method summary listing), available to us, is shown.

Method Summaries:

get(anIndex) -- returns elem at passed "anIndex"
isEmpty() -- returns true if this array is empty
size() -- returns size (number of elements)

Method 'first' (DynamicArray)

Here is an algorithm for the "first" method.

The algorithm gets and returns the first element.

Does the algorithm work harder as it grows?

No, size does not change the work (effort) expended by this algorithm.

We can see that the work does not change as size changes -- size is not a "player" here.

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

Let's say we are doing Big-O analysis on the algo for a "linear search".

Let us pretend the is growing in size towards infinity.

Does the algorithm work harder as it grows?

Certainly yes.

The structure size [e.g. "this.size()"] controls how many times we could loop.

Bottom line: growth in "size" makes this algo work harder.

Also remember we assume Worst Case

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
}

Number of Operations

"Operations" is steps/statements that are executed in our algorithm (i.e. how hard the algo works)
We do not want to "measure" operations.
We do want to analyze how the algo work (effort) changes relative to structure size growth

Big-O Levels and T-Shirts

One thousand people would probably have one thousand (if precisely measured) different shirt sizes. But when we choose tee shirts we broadly group this into something like (Small, Medium, Large).

Big-O is similar. We do not make exact measurements or operation counts. What we do is determine the grouping (performance level) that a given algorithm belongs to.

Data Structures And Algorithms (DSA) (Chapter 105 - Intro to Big-O)

Chapter 105 - Intro to Big-O < Prev Concepts > CHAP101 Next >

Index Intro Concepts Notations Tips Analysis-Types Summary Space Refs

Chapter Top Search Site Contents