Big O Notation Cheat Sheet

Big O Notation	Description	Example Data Structures/Algorithms
O(1)	Constant time	HashMap lookup, Stack push/pop, Queue enqueue/dequeue
O(log n)	Logarithmic time	Binary Search, Balanced Binary Search Trees (e.g., AVL Tree)
O(n)	Linear time	Traversing a Linked List, Linear Search, Unsorted Array Search
O(n log n)	Linearithmic time	Merge Sort, Heap Sort, Quick Sort (average case)
O(n^2)	Quadratic time	Bubble Sort, Insertion Sort, Selection Sort
O(2^n)	Exponential time	Solving the Tower of Hanoi, Recursive Fibonacci
O(n!)	Factorial time	Solving the Traveling Salesman Problem (brute force)

Breadth-First Search (BFS) vs Depth-First Search (DFS):

Breadth-First Search (BFS)

How it works: BFS explores the graph level by level. It starts at the root node (or any arbitrary node in a graph) and explores all of its neighbors before moving on to the next level. This process continues until all nodes have been explored. BFS uses a queue to keep track of the next nodes to visit.

Steps:

Start at the root node (or any start node). Enqueue the start node in a queue. Dequeue a node, process it, and enqueue all its unvisited neighbors. Repeat until the queue is empty. Use cases: Shortest path in an unweighted graph, level-order traversal of trees.

Depth-First Search (DFS)

How it works: DFS explores as far down a branch as possible before backtracking. It dives deep into one branch of the tree or graph, then backtracks to explore another branch. DFS uses a stack (can be implemented recursively with function calls or explicitly with a stack data structure) to keep track of the nodes to visit.

Steps:

Start at the root node (or any start node). Push the start node to a stack. Pop a node, process it, and push all its unvisited neighbors (if there are any). Repeat until the stack is empty or all nodes are processed. Use cases: Pathfinding in mazes, topological sorting, detecting cycles in graphs.

Big O Notation Explanation:

Time Complexity (BFS and DFS): Both have a time complexity of O(V + E), where V is the number of vertices and E is the number of edges in the graph. This is because in the worst case, you will visit every vertex and every edge.

Space Complexity (BFS): BFS needs to store all the vertices at the current level in the queue, so in the worst case (e.g., a full binary tree), it takes up O(V) space.

Space Complexity (DFS): DFS may store all the recursive calls or nodes in the stack, which also leads to O(V) space complexity, but DFS tends to use less memory than BFS in large, shallow graphs.

So yeah, whether you want to swim through the shallow end (BFS) or deep dive till you hit the bottom (DFS), they both have their charm—just pick your poison!

Search Algorithm	Practical Uses
BFS	- Finding the shortest path in unweighted graphs (e.g., social networks, road maps).
	- Level-order traversal in trees (e.g., solving puzzles like the 8-puzzle).
	- Web crawlers (exploring layers of URLs starting from a seed).
	- Peer-to-peer networks (finding the closest node).
	- Broadcasting in network routers.
	- Finding connected components in a graph.
DFS	- Pathfinding in mazes or puzzles (exploring all possible solutions).
	- Detecting cycles in a graph.
	- Topological sorting (used in scheduling tasks).
	- Solving problems like Sudoku (backtracking).
	- Checking for bipartiteness in a graph.
	- Finding strongly connected components in a graph (using Kosaraju’s or Tarjan’s algorithms).

Examples

DFS

Here’s a canonical example of Depth-First Search (DFS) in Java, used for solving a maze (a graph traversal problem):

Problem: You are given a maze represented by a 2D grid, where 1 represents walls and 0 represents paths. You start at the top-left corner (0,0) and want to determine if there is a path to the bottom-right corner of the maze (n-1, m-1).

public class MazeSolver {

    // Directions: right, down, left, up
    private static final int[][] DIRECTIONS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    public static void main(String[] args) {
        int[][] maze = {
            {0, 1, 0, 0, 0},
            {0, 1, 0, 1, 0},
            {0, 0, 0, 1, 0},
            {1, 1, 0, 0, 0},
            {0, 0, 0, 1, 0}
        };

        boolean pathExists = hasPath(maze, 0, 0, new boolean[maze.length][maze[0].length]);
        System.out.println("Path exists: " + pathExists);
    }

    public static boolean hasPath(int[][] maze, int x, int y, boolean[][] visited) {
        // Base cases: out of bounds, hitting a wall, or already visited
        if (x < 0 || y < 0 || x >= maze.length || y >= maze[0].length || maze[x][y] == 1 || visited[x][y]) {
            return false;
        }

        // If the destination is reached, return true
        if (x == maze.length - 1 && y == maze[0].length - 1) {
            return true;
        }

        // Mark the cell as visited
        visited[x][y] = true;

        // Explore in all four directions (right, down, left, up)
        for (int[] direction : DIRECTIONS) {
            int newX = x + direction[0];
            int newY = y + direction[1];
            if (hasPath(maze, newX, newY, visited)) {
                return true;
            }
        }

        // Backtrack and mark the cell as unvisited (not strictly necessary in this case)
        visited[x][y] = false;

        return false;
    }
}

Explanation:

• The maze is represented by a 2D grid where 0 indicates a path and 1 represents a wall.

• The hasPath function uses DFS to explore all four directions (right, down, left, up) from each cell.

• If the bottom-right corner of the maze is reached, the function returns true. Otherwise, it backtracks and continues searching until all possible paths are explored.

• The visited array ensures we don’t revisit the same cell, preventing infinite loops.

Big O Complexity:

• Time Complexity: O(V + E), where V is the number of cells (vertices) and E is the number of connections (edges).

• Space Complexity: O(V) due to the recursion stack and the visited array.

DFS

Here’s a canonical example of Breadth-First Search (BFS) in Java, also used for solving a maze traversal problem:

Problem: You are given a maze represented by a 2D grid, where 1 represents walls and 0 represents paths. You start at the top-left corner (0,0) and want to determine if there is a path to the bottom-right corner of the maze (n-1, m-1).

import java.util.LinkedList;
import java.util.Queue;

public class MazeSolverBFS {

    // Directions: right, down, left, up
    private static final int[][] DIRECTIONS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    public static void main(String[] args) {
        int[][] maze = {
            {0, 1, 0, 0, 0},
            {0, 1, 0, 1, 0},
            {0, 0, 0, 1, 0},
            {1, 1, 0, 0, 0},
            {0, 0, 0, 1, 0}
        };

        boolean pathExists = hasPathBFS(maze);
        System.out.println("Path exists: " + pathExists);
    }

    public static boolean hasPathBFS(int[][] maze) {
        if (maze == null || maze.length == 0 || maze[0].length == 0) {
            return false;
        }

        int rows = maze.length;
        int cols = maze[0].length;

        boolean[][] visited = new boolean[rows][cols];
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{0, 0}); // Start from the top-left corner
        visited[0][0] = true;

        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int x = current[0];
            int y = current[1];

            // If we reached the bottom-right corner, return true
            if (x == rows - 1 && y == cols - 1) {
                return true;
            }

            // Explore in all four directions
            for (int[] direction : DIRECTIONS) {
                int newX = x + direction[0];
                int newY = y + direction[1];

                if (newX >= 0 && newX < rows && newY >= 0 && newY < cols &&
                    maze[newX][newY] == 0 && !visited[newX][newY]) {
                    queue.offer(new int[]{newX, newY});
                    visited[newX][newY] = true; // Mark the cell as visited
                }
            }
        }

        return false; // No path found
    }
}

Explanation: The maze is represented by a 2D grid, where 0 indicates a path and 1 represents a wall. The hasPathBFS function uses BFS to explore all possible routes, level by level, starting from the top-left corner. A queue is used to track the current cell being processed and its neighbors. The algorithm explores the closest cells first before expanding further. The visited array ensures that each cell is processed only once, preventing infinite loops. If the bottom-right corner is reached, the function returns true. Otherwise, it continues until all paths are explored or the queue is empty. Big O Complexity: Time Complexity: O(V + E), where V is the number of cells (vertices) and E is the number of connections (edges). Space Complexity: O(V), as we store the visited nodes and the queue. BFS is ideal when you want to find the shortest path in an unweighted grid like t

Comments

comments powered by Disqus