Data Structures & Algorithms

An asymptotic upper bound describing how an algorithm's running time or space grows relative to input size n as n grows large, ignoring constants and lower-order terms.

Ω(g) is an asymptotic lower bound (best case growth). Θ(g) is a tight bound: the function grows exactly like g (both upper and lower). O(g) is the upper bound.

O(1). Arrays store elements in contiguous memory, so the address of index i is computed by base + i * elementSize, giving constant-time random access.

O(1) on average, assuming a good hash function and load factor. Worst case is O(n) when many keys collide into one bucket.

Separate chaining (each bucket holds a linked list/structure of colliding entries) and open addressing (probe for the next free slot via linear, quadratic, or double hashing).

A linear structure with LIFO (Last In, First Out) ordering. push adds to the top, pop removes from the top; both are O(1). Used for call stacks, undo, and DFS.