# What is the asymptotic computational complexity?

by Stephen M. Walker II, Co-Founder / CEO

## What is asymptotic computational complexity?

Asymptotic computational complexity is a concept in computational complexity theory that uses asymptotic analysis to estimate the computational complexity of algorithms and computational problems. It's often associated with the use of big O notation, which provides an upper bound on the time or space complexity of an algorithm as the input size grows.

The term "asymptotic" refers to the behavior of a function as its input (usually denoted as 'n') gets large. This is important because we're typically interested in how an algorithm will perform on large inputs. For example, an algorithm is said to have a time complexity of O(n^2) (read as "order n squared") if there is a fixed constant 'c' such that for all 'n', the algorithm takes time at most c*n^2 on inputs of size 'n'.

There are three main types of asymptotic notations used in computational complexity:

1. Big O Notation (O-notation): Represents the upper bound of the running time of an algorithm, providing the worst-case complexity.
2. Omega Notation (Ω-notation): Represents the lower bound of the running time of an algorithm, providing the best-case complexity.
3. Theta Notation (Θ-notation): Represents both the lower bound and the upper bound of the running time of an algorithm, providing the average-case complexity. It's used when the asymptotic upper and lower bounds coincide.

Asymptotic complexity is independent of hardware and doesn't depend on machine-specific constants, making it a useful tool for comparing the efficiency of different algorithms. However, it's important to note that these estimates are usually only accurate up to a constant factor, and we often ignore constant factors when comparing asymptotic running times.

## Understanding Asymptotic Computational Complexity

Asymptotic computational complexity is a fundamental concept in computer science that describes how the resource requirements of an algorithm, such as time or space, scale with the size of the input. It's crucial for predicting algorithm performance on large inputs and for comparing different algorithms.

Big O notation is the most prevalent method for expressing this complexity, focusing on the worst-case scenario. For instance, O(n) indicates that the algorithm's running time increases linearly with the input size. Other common complexity classes include O(1) for constant time, O(log n) for logarithmic time, O(n log n) for log-linear time, and O(n^2) for quadratic time.

AI algorithms typically exhibit high complexity due to their search-based nature, which requires exploring vast solution spaces. Nonetheless, some AI algorithms are optimized for efficiency, resulting in lower complexity. For example, using appropriate data structures or leveraging characteristics of the input can significantly reduce an algorithm's complexity.

The complexity class of an algorithm provides a lower bound for its efficiency, primarily considering the worst-case scenario. However, practical performance often exceeds this theoretical minimum. For instance, an algorithm with a complexity of O(log n) suggests that its running time increases logarithmically with input size, which is the case for many efficient search algorithms.

## More terms

### What is a network motif?

A network motif is a recurring, statistically significant subgraph or pattern within a larger network graph. These motifs are found in various types of networks, including biological, social, and technological systems. They are considered to be the building blocks of complex networks, appearing more frequently than would be expected in random networks. Network motifs can serve as elementary circuits with defined functions, such as filters, pulse generators, or response accelerators, and are thought to be simple and robust solutions that have been favored by evolution for their efficiency and reliability in performing certain information processing tasks.

### What is AI Planning (Automated Planning & Scheduling)?

AI Planning, also known as Automated Planning and Scheduling, is a branch of artificial intelligence that focuses on the development of strategies or sequences of actions to achieve specific goals. It is typically used for execution by intelligent agents, autonomous robots, and unmanned vehicles.