Q2: Asymptotic Notation & Amortized Complexity. - DSA Patterns (Multi-Lang)

In Simple Words:

Big-O ($O$): Upper bound / worst-case execution time.
Big-$\Omega$ ($\Omega$): Lower bound / best-case execution time.
Big-$\Theta$ ($\Theta$): Tight bound (upper and lower bounds match within constant factors).
Amortized Analysis: Average time per operation over a long sequence. Dynamic arrays double their capacity when full: individual resizes take $O(N)$, but occur so rarely that amortized cost per append is strictly $O(1)$.

Multi-Language SolutionsPython 3 • JavaScript • TypeScript • Java • C++

Switch tabs or choose All

class DynamicArray:
    def __init__(self):
        self.capacity = 2
        self.size = 0
        self.data = [None] * self.capacity

    def push(self, val):
        if self.size == self.capacity:
            # Amortized O(1): double capacity when full
            self.capacity *= 2
            new_data = [None] * self.capacity
            for i in range(self.size):
                new_data[i] = self.data[i]
            self.data = new_data
        self.data[self.size] = val
        self.size += 1