Category: Algorithms & Complexity
-
Overview Time complexity is a theoretical measure that describes the amount of computer time it takes to run an algorithm as a function of the length of the input. Instead of measuring actual seconds (which vary by hardware), time complexity counts the number of elementary operations performed. Core Concepts Elementary Operations: Operations that take a…
-
Overview Sorting is the process of arranging a collection of data in a specific order (ascending or descending). Efficient sorting is fundamental to many other algorithms, such as Binary Search. Core Concepts Stability: A sort is stable if it preserves the relative order of records with equal keys. In-Place: An algorithm is in-place if it…
-
Overview Search algorithms are methods used to retrieve information stored within some data structure. The efficiency of a search depends heavily on how the data is organized. Core Concepts Linear Search: Checks every element in sequence. Works on unsorted data. Time: $O(n)$. Binary Search: Repeatedly divides a sorted search interval in half. Works only on…
-
Overview A Greedy Algorithm is an algorithmic paradigm that builds up a solution piece by piece, always choosing the next piece that offers the most obvious and immediate benefit. It makes a locally optimal choice in the hope that this will lead to a globally optimal solution. Core Concepts Greedy Choice Property: A global optimum…
-
Overview Dynamic Programming (DP) is an optimization technique used to solve complex problems by breaking them down into simpler, overlapping subproblems and storing the results of these subproblems to avoid redundant calculations. Core Concepts Optimal Substructure: A problem has optimal substructure if the optimal solution to the problem contains optimal solutions to its subproblems. Overlapping…
-
Overview Big O notation is a mathematical notation used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity. In computer science, it is used to classify algorithms according to how their run time or space requirements grow as the input size ($n$) grows. Core Concepts Time…
-
Overview Backtracking is a general algorithmic technique for finding all (or some) solutions to some computational problems, notably constraint satisfaction problems. It incrementally builds candidates for solutions and abandons a candidate (“backtracks”) as soon as it determines that the candidate cannot possibly be completed to a valid solution. Core Concepts State-Space Search: Exploring all possible…