Data Structures & Algorithms

What type of data management does a Stack use?

Last In First Out (LIFO)

What does the push operation do to a stack?

Add’s an element to the top of a stack, in terms of a dynamic array means at the end of it.

What does the pop operation do to a stack?

Removes the last element from the top of the stack, which in dynamic array’s means removing the last element in the array.

What does the peek operation do to a stack?

It returns the top element of the stack without removing it.

What is the Big O for the peek operation in a stack?

O(1) operation; Constant Time Complexity

What is the Big O for the pop operation in a stack?

O(1) operation; Constant Time Complexity

What is the Big O for the push operation in a stack?

O(1) operation; Constant Time Complexity

Big O Notation

Describes the upper bound of an algorithm's growth rate, usually the worst-case time or space as input size grows.

Big Omega (Ω)

Describes the lower bound of an algorithm's growth rate, usually the best case.

Big Theta (Θ)

Describes a tight bound, meaning the algorithm grows at exactly that rate (both upper and lower bound).

Time Complexity

How the number of operations an algorithm performs grows as the input size grows.

Space Complexity

How much extra memory an algorithm needs as the input size grows.

O(1) – Constant Time

Runtime stays the same no matter the input size.

O(log n) – Logarithmic Time

Runtime grows slowly because the problem is cut in half each step.

O(n) – Linear Time

Runtime grows directly with input size.

O(n log n) – Linearithmic Time

Typical of efficient sorting algorithms.

O(n²) – Quadratic Time

Runtime grows with the square of the input, often from nested loops.

O(2ⁿ) – Exponential Time

Runtime doubles with each additional input element.

O(n!) – Factorial Time

Runtime grows extremely fast, from trying every possible ordering.

Worst Case

The maximum number of operations an algorithm could take for an input of size n.

Best Case

The minimum number of operations an algorithm could take for an input of size n.

Average Case

The expected number of operations over all possible inputs of size n.

Drop the Constants

In Big O, constant multipliers are ignored. O(2n) simplifies to O(n).

Drop Non-Dominant Terms

Only the fastest-growing term is kept. O(n² + n) simplifies to O(n²).

Amortized Time

The average cost per operation over a sequence of operations, even if some are occasionally expensive.

Adding Complexities

When steps happen one after another, add them: O(A + B).

Multiplying Complexities

When one step happens inside another (nested), multiply them: O(A × B).

Asymptotic Analysis

Studying how an algorithm behaves as input size approaches infinity.

Common Order (fastest to slowest)

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)