Time complexity
{% hint style="info" %} In computer science, computational complexity is the study of how efficiently a problem can be solved algorithmically. {% endhint %}
- O(1): constant time, meaning that the time taken by the algorithm does not depend on the size of the input
- O(log n): logarithmic time, meaning that the time taken by the algorithm grows logarithmically with the size of the input
- O(n): linear time, meaning that the time taken by the algorithm grows linearly with the size of the input
- O(n log n): quasilinear time, meaning that the time taken by the algorithm grows near-linearly with the size of the input
- O(n^2): quadratic time, meaning that the time taken by the algorithm grows quadratically with the size of the input
- O(2^n): exponential time, meaning that the time taken by the algorithm grows exponentially with the size of the input
In general, we aim to design algorithms with the smallest possible time and space complexity, as this will allow us to solve larger and more complex problems efficiently.
Topics in algorithms research
- Machine learning algorithms: Machine learning is a rapidly growing field that involves training computers to learn patterns in data and make predictions or decisions based on that data. There are a variety of algorithms used in machine learning, including deep learning algorithms, reinforcement learning algorithms, and decision tree algorithms.
- Graph algorithms: Graph algorithms are used to analyze relationships between entities in a network. Some common graph algorithms include Dijkstra's shortest path algorithm, the Bellman-Ford algorithm, and the Floyd-Warshall algorithm.
- Approximation algorithms: Approximation algorithms are used to find near-optimal solutions to problems that are computationally difficult to solve exactly. These algorithms trade off optimality for efficiency, providing solutions that are close to optimal while running in polynomial time.
- Online algorithms: Online algorithms are used in situations where the input data is received in a stream or online fashion, and decisions must be made in real-time without knowledge of future input. Examples of online algorithms include the paging algorithm and the k-server algorithm.
- Randomized algorithms: Randomized algorithms use randomness as a tool to solve problems more efficiently or accurately than deterministic algorithms. Examples of randomized algorithms include the randomized quicksort algorithm and the Monte Carlo algorithm.
- Parallel algorithms: Parallel algorithms are designed to take advantage of parallel computing architectures, allowing multiple computations to be performed simultaneously. Some common parallel algorithms include the parallel merge sort algorithm and the parallel matrix multiplication algorithm.