DEV Community: Utku Catal

Space Complexity + Ω and Θ Notations

Utku Catal — Sat, 23 May 2026 09:51:00 +0000

Time isn't everything. Memory matters too. Space complexity measures the extra memory an algorithm needs as input grows. A fast algorithm that allocates gigabytes is not actually fast in production.

Space Complexity Examples

// O(1) - Constant space
func reverseString(s []byte) {
    for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
        s[i], s[j] = s[j], s[i]
    }
}

// O(n) - Linear space (hash map)
func twoSum(nums []int, target int) []int {
    m := make(map[int]int)
    for i, num := range nums {
        complement := target - num
        if val, ok := m[complement]; ok {
            return []int{val, i}
        }
        m[num] = i
    }
    return nil
}

// O(n) recursion stack
func factorial(n int) int {
    if n <= 1 {
        return 1
    }
    return n * factorial(n-1) // n stack frames
}

Three things to track for space:

Auxiliary data structures: the hash map in twoSum is O(n).
Call stack: recursion adds frames; factorial(n) uses O(n) stack.
Input itself: usually excluded from space complexity (we measure extra memory).

Time vs. Space Trade-offs

These almost always trade off against each other.

Memoization: trade space (cache) for time (no recomputation).
In-place algorithms: trade time (more passes) for space (no extra allocation).
Streaming: trade exactness (approximate counts) for space (constant).

Advanced Notations

Big O is the most famous, but it's only one of a family:

O(n), Big O: Upper bound. "Grows no faster than n." Worst case.
Ω(n), Big Omega: Lower bound. "Grows at least as fast as n." Best case.
Θ(n), Big Theta: Tight bound. "Grows exactly like n." Both upper and lower.
o(n), Little-o: Strict upper bound. "Grows strictly slower than n."

Why Θ Matters

When an algorithm is Θ(n log n), the lower and upper bounds match. There is no edge case where it suddenly becomes faster or slower. Merge sort is Θ(n log n) in time and Θ(n) in auxiliary space.

Most engineers reach for Big O. But when you see a paper or textbook use Θ, it's a stronger claim: this is the tight characterization, not just an upper limit.

Conclusion

Time and space complexity are two halves of the same question: how does my algorithm scale? Ω, Θ, and little-o sharpen the answer when Big O is too vague. Together, they let you predict performance before a single line of production code runs.

Next up: the cheatsheet with every notation in one place.

O(2ⁿ) & O(n!): Algorithms to Avoid

Utku Catal — Thu, 14 May 2026 12:29:11 +0000

Exponential growth destroys performance. O(2ⁿ) and O(n!) represent computational nightmares. Recognizing them early is a survival skill. They can turn a "five-second feature" into a server that never returns.

O(2ⁿ): Naive Fibonacci

Each call branches into two. Calls explode with depth.

func fib(n int) int {
    if n <= 1 {
        return n
    }
    return fib(n-1) + fib(n-2) // 2^n calls!
}

func main() {
    fmt.Println(fib(40)) // Takes forever!
}

The problem: fib(40) recomputes the same subproblems billions of times. There's no memory of past work.

Fix with Memoization (O(n))

Cache results. Each subproblem is solved once.

var memo = map[int]int{}

func fibMemo(n int) int {
    if val, ok := memo[n]; ok {
        return val
    }
    if n <= 1 {
        return n
    }
    memo[n] = fibMemo(n-1) + fibMemo(n-2)
    return memo[n]
}

Same algorithm shape, but the cache collapses the exponential tree into a linear walk. This is the heart of dynamic programming.

O(n!): Permutations

Generating all arrangements of n items: n × (n-1) × ... × 1.

func permute(nums []int) [][]int {
    var result [][]int
    permutation(nums, []int{}, &result)
    return result
}

func permutation(nums, path []int, result *[][]int) {
    if len(nums) == 0 {
        temp := make([]int, len(path))
        copy(temp, path)
        *result = append(*result, temp)
        return
    }
    for i, v := range nums {
        newNums := append(append(nums[:i], nums[i+1:]...), 0)
        newNums = newNums[:len(newNums)-1]
        permutation(newNums, append(path, v), result)
    }
}

The math is brutal:

n=10 → 3.6 million permutations
n=15 → 1.3 trillion, practically impossible
n=20 → outlives the universe

When You Hit Exponential

If your algorithm is exponential or factorial, ask:

Can I memoize? Repeated subproblems → cache them.
Can I prune? Branch-and-bound, A*, alpha-beta pruning skip dead branches.
Do I actually need all results? Often "any valid" beats "all valid."
Is this NP-hard? Then accept an approximation algorithm.

Conclusion

Exponential and factorial complexity isn't theoretical. It shows up in naive recursion, brute-force search, and permutation problems. Recognize the shape, then apply memoization, pruning, or a better algorithm before it ships to production.

Next up: space complexity and the lesser-known Ω and Θ notations.

O(log n) & O(n log n): Search and Sort Masters

Utku Catal — Wed, 13 May 2026 19:14:17 +0000

Searching and sorting power modern applications. O(log n) and O(n log n) represent optimal efficiency for these tasks. Knowing them is the difference between a search that returns instantly and one that crawls.

O(log n): Binary Search

Halves the search space each step. Logarithmic growth. To find an element among 1 million sorted items, only ~20 comparisons.

func binarySearch(arr []int, target int) int {
    left, right := 0, len(arr)-1
    for left <= right { // log n iterations
        mid := left + (right-left)/2
        if arr[mid] == target {
            return mid
        }
        if arr[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return -1
}

The trick: with each iteration, half of the remaining candidates are eliminated. Requires a sorted input.

O(n log n): Merge Sort

Divide-and-conquer: splits array, sorts halves, merges. Industry standard for general-purpose sorting.

func mergeSort(arr []int) []int {
    if len(arr) <= 1 {
        return arr
    }
    mid := len(arr) / 2
    left := mergeSort(arr[:mid])
    right := mergeSort(arr[mid:])
    return merge(left, right)
}

func merge(left, right []int) []int {
    result := make([]int, 0, len(left)+len(right))
    i, j := 0, 0
    for i < len(left) && j < len(right) {
        if left[i] < right[j] {
            result = append(result, left[i])
            i++
        } else {
            result = append(result, right[j])
            j++
        }
    }
    return append(append(result, left[i:]...), right[j:]...)
}

Real-World Usage

Go's sort.Slice() uses similar O(n log n) algorithms (Introsort, a hybrid of quicksort, heapsort, and insertion sort). This is the sweet spot: fast enough for production, simple enough to reason about.

Binary search trees, B-trees: O(log n) lookups
Merge sort, heapsort, quicksort (avg): O(n log n)
Database indexes: built around these complexities

Conclusion

When you see O(log n), think "halving." When you see O(n log n), think "divide, conquer, combine." These two complexities are the workhorses of efficient data access. Most production-grade algorithms live here.

Next up: the complexities to avoid, O(2ⁿ) and O(n!).

Time Complexity 101: O(1), O(n), O(n )

Utku Catal — Tue, 12 May 2026 18:09:50 +0000

Modern algorithms can be complex. Big O Notation helps developers measure performance by analyzing how runtime grows with input size. Understanding O(1), O(n), and O(n²) is essential for writing efficient code.

Big O describes the worst-case scenario. It captures how an algorithm scales as n (input size) increases.

O(1): Constant Time

Accessing an array element by index. Always 1 operation regardless of size.

package main
import "fmt"

func getFirst(arr []int) int {
    return arr[0] // Always O(1)
}

func main() {
    arr := []int{10, 20, 30, 40}
    fmt.Println(getFirst(arr)) // Output: 10
}

O(n): Linear Time

Scanning an entire array. Operations grow proportionally with n.

func findMax(arr []int) int {
    max := arr[0]
    for i := 1; i < len(arr); i++ { // n iterations
        if arr[i] > max {
            max = arr[i]
        }
    }
    return max
}

O(n²): Quadratic Time

Nested loops. Disastrous for large n (n=1000 → 1M operations).

func bubbleSort(arr []int) []int {
    n := len(arr)
    for i := 0; i < n-1; i++ {
        for j := 0; j < n-i-1; j++ { // n*n iterations
            if arr[j] > arr[j+1] {
                arr[j], arr[j+1] = arr[j+1], arr[j]
            }
        }
    }
    return arr
}

Why It Matters

O(n²) works for n=100 but crashes at n=10,000. Choosing the right complexity class is the difference between a feature that scales and one that times out under load.

O(1): instant, regardless of input
O(n): predictable, scales linearly
O(n²): fine for small inputs, deadly at scale

Conclusion

Time complexity is the language engineers use to reason about performance before writing a single benchmark. Master O(1), O(n), and O(n²) first. They show up in nearly every algorithm you'll touch.

Next up: O(log n) and O(n log n), the complexities that power search and sort.

What is Object-Oriented Programming (OOP)?

Utku Catal — Mon, 11 May 2026 21:09:33 +0000

Modern software systems can be complex. Object-Oriented Programming (OOP) is one of the most widely used programming paradigms that helps developers manage this complexity by modeling real-world entities as objects. These objects combine data and behavior, making complex systems easier to design and maintain.

OOP is built around several core concepts such as class, inheritance, encapsulation, and polymorphism. These concepts help developers to write code that is more modular, reusable, and maintainable.

Let’s take a quick look at what they mean:

Class: A class is a blueprint for creating objects. It defines the properties (attributes) and behaviors (methods) that the objects created from it will have.

For example, consider a class called Computer. There may be many computers with different brands, types, and models, but all of them share the same properties: motherboard, CPU, GPU, and PSU. Here, Computer is the class, and motherboard, CPU, GPU, and PSU are attributes of the class.

Usage:

// Class definition
class Computer {
    public $motherboard;
    public $cpu;
    public $gpu;
    public $psu;

    // Constructor to initialize properties
    public function __construct($motherboard, $cpu, $gpu, $psu) {
        $this->motherboard = $motherboard;
        $this->cpu = $cpu;
        $this->gpu = $gpu;
        $this->psu = $psu;
    }

    // Method to display computer specs
    public function showSpecs() {
        echo "Motherboard: " . $this->motherboard . "\n";
        echo "CPU: " . $this->cpu . "\n";
        echo "GPU: " . $this->gpu . "\n";
        echo "PSU: " . $this->psu . "\n";
    }
}

// Creating an instance (object) of Computer
$myPC = new Computer("ASUS ROG", "Intel i7", "NVIDIA RTX 4070", "Corsair 750W");

// Using the object
$myPC->showSpecs();

Inheritance: Inheritance allows a class to acquire the properties and methods of another class. This promotes code reuse and helps establish a hierarchical relationship between classes.

For example, you might have a base class called Device and a derived class called Computer. The Computer class can inherit common properties such as powerStatus or brand from Device, while also defining its own specific attributes like GPU or CPU.

Encapsulation: Encapsulation is the practice of restricting direct access to an object’s internal data and instead exposing it through controlled methods. This helps protect the integrity of the data and prevents unintended interference.

In many programming languages, this is achieved using access modifiers such as private, protected, and public. For instance, instead of directly modifying a Computer’s CPU property, you might use a setter method to ensure only valid values are assigned.

Polymorphism: Polymorphism allows objects of different classes to be treated as objects of a common superclass. It enables a single interface to represent different underlying forms (data types).

For example, multiple classes like Desktop and Laptop can implement a method called getPowerUsage(), but each class can provide its own implementation. The same method name behaves differently depending on the object that calls it.

Simple Example:

class Device {
    public function start() {
        echo "Device is starting...\n";
    }
}

class Computer extends Device {
    public function start() {
        echo "Computer is booting up...\n";
    }
}

class Laptop extends Device {
    public function start() {
        echo "Laptop is powering on...\n";
    }
}

// Polymorphism in action
$devices = [new Computer(), new Laptop()];

foreach ($devices as $device) {
    $device->start();
}

Explanation: In this example, both Computer and Laptop override the start() method from the Device class. Even though they share the same method name, each class provides its own behavior. This is a simple demonstration of polymorphism.

Why It Matters

OOP provides a structured approach to software development. By organizing code into objects, developers can better manage complexity, especially in large-scale applications.

It improves code reusability through inheritance.
It enhances security and data integrity via encapsulation.
It allows flexibility and scalability with polymorphism.
It makes code easier to maintain, test, and extend.

In real-world projects, these benefits translate into faster development cycles, fewer bugs, and cleaner architecture.

Conclusion

Object Oriented Programming is a powerful paradigm that helps developers model complex systems in a clear and organized way. By understanding and applying its core principles: class, inheritance, encapsulation, and polymorphism, you can write code that is not only functional but also scalable and maintainable.

As software systems continue to grow in size and complexity, mastering OOP becomes an essential skill for any modern developer.

*paradigm: A paradigm is a standard, perspective, model, or set of ideas that acts as a pattern for how something is viewed, made, or understood