Lesson

Complexity of Operations

Big-O notation describes how an operation's cost grows with input size $n$. Constant time $O(1)$ does not depend on $n$; linear time $O(n)$ grows in proportion; logarithmic time $O(\\log n)$ grows very slowly.

Practice

Q1

What is the time complexity of accessing an array element by index?

Q2

What is the worst-case time of a linear search over $n$ items?

Show hint

In the worst case you inspect every element.

Choosing the right data structure changes an operation's complexity. The table of common operations is worth committing to memory.

Quiz

Q1

What is the time complexity of binary search on a sorted array?

Show hint

Each comparison halves the search range.

Q2

What is the average-case lookup time in a hash table?

Show hint

A good hash gives expected constant time.

Q3

What is the worst-case time of bubble sort?

Show hint

Nested passes over the data.