Algorithms
An algorithm is a finite procedure used for solving a problem or performing a computation.
Algorithm Analysis - What's "Big O" Notation?
Algorithm analysis is an important part of a broader computational complexity theory, which provides theoretical estimates for the resources needed by any algorithm which solves a given computational problem. These estimates provide an insight into reasonable directions of search for efficient algorithms. Maybe you've heard of "Big O" notation before; it's a way of describing how the runtime of an algorithm scales with the size of the input in the worst case (more on that below).
This entire section will eventually be its own page, but for now, it will be a part of the Algorithms section. In the meantime, a brief overview is provided on algorithm analysis.
Time & Space Complexity - Why Growth Rate Matters
Time complexity quantifies the runtime of an algorithm by counting elementary operations, each taking a fixed time. This measure ensures that the time taken and the number of operations differ by at most a constant factor. On the other hand, space complexity gauges the working storage an algorithm requires, measured by the number of memory locations used to store data, rather than the actual space utilized in those locations.
Growth rate matters because it determines how well an algorithm scales with the size of the input. For example, if an algorithm has a time complexity of O(n2), then the runtime of the algorithm will increase quadratically as the size of the input increases.
Big O Notation
Big O notation is a mathematical notation that characterizes functions according to their worst-case growth rates. Let f(n) and g(n) be two functions defined on some subset of the real numbers. One writes f(n) = O(g(n)) if and only if there exist positive constants n0 and c such that f(n) ≤ cg(n) for all n ≥ n0.
Big Omega (Ω) Notation
Omega notation is a notation used for describing the best-case runtime of functions. It is used primarily for asymptotic lower bounds, that is, to describe the behavior of the function when the argument tends towards a particular value or infinity. Let f(n) and g(n) be two functions defined on some subset of the real numbers. One writes f(n) = Ω(g(n)) if and only if there exist positive constants n0 and c such that f(n) ≥ cg(n) for all n ≥ n0.
Big Theta (Θ) Notation
Theta notation is a notation used for describing the average-case runtime of functions. It is used primarily for asymptotic tight bounds, that is, to describe the behavior of the function when the argument tends towards a particular value or infinity. Let f(n) and g(n) be two functions defined on some subset of the real numbers. One writes f(n) = Θ(g(n)) if and only if there exist positive constants n0, c1, and c2 such that c1g(n) ≤ f(n) ≤ c2g(n) for all n ≥ n0.
Nine Important Functions
There are nine functions that are commonly used in algorithm analysis. They are listed below:
- Constant - O(1)
- Linearithmic - O(n log n)
- Exponential - O(2n)
- Logarithmic - O(log n)
- Quadratic - O(n2)
- Factorial - O(n!)
- Linear - O(n)
- Cubic - O(n3)
- Polynomial - O(nk)
These functions are listed in order of increasing complexity. The constant function is the simplest function, and the polynomial function is the most complex function. The constant function is the fastest function, and the polynomial function is the slowest function.
Reduction of coefficients
When analyzing the time complexity of an algorithm, the coefficients of the terms are ignored. For example, if an algorithm has a time complexity of 5n2 + 3n + 2, then the time complexity is O(n2). The coefficients of the terms are ignored because they do not affect the growth rate of the function.
Sorting Algorithms
Sorting is the process of arranging elements in a specific order and it's a fundamental concept in computer science and is used in many applications. Some sorting algorithms are better on larger data sets and some are better with smaller datasets of only a few thousand elements. The time complexity of a sorting algorithm is a measure of how well it scales with the size of the data set. The space complexity of a sorting algorithm is a measure of how much auxiliary memory it uses.
Some sorting algorithms sort in place, meaning that they don't use any auxiliary memory. Other sorting algorithms are not in place, meaning that they use auxiliary memory. Sorting algorithms can also be stable or unstable. A stable sorting algorithm preserves the relative order of elements with equal keys. An unstable sorting algorithm does not preserve the relative order of elements with equal keys.
Pathfinding Algorithms
The purpose of a pathfinding algorithm is to find the shortest path between two points. They are used in many applications such as GPS navigation, video games, and robotics. There are many different pathfinding algorithms, but the most common ones are Dijkstra's algorithm and A* star algorithm. Paths can be expressed as a sequence of nodes, edges, or both.
Pathfinding algorithms make use of search contours, which are the nodes that are currently being explored. Some algorithms only require the problem space to be represented as a graph and then coded, such as Dijkstra's algorithm. Other algorithms like A* Star require the problem space to be represented as a graph and then coded. For example, designing a good heuristic, a key part of A* star algorithm, takes time and effort.