AI Glossary / Computer vision and multimodal AI / Intermediate

Computational complexity

Definition

Computational complexity studies how the resources required for a computation grow with input size. It commonly examines time and memory, helping distinguish algorithms that remain manageable as problems grow from those whose resource demands increase too quickly for the intended application.

What it means

An algorithm that takes one second on a small example may take minutes, days or longer when the input grows. Complexity analysis asks how that growth behaves, rather than reporting only one measured runtime. A linear-time method roughly scales with the number of input items, while a quadratic method can grow with the number of item pairs. Complexity theory also classifies problems according to the resources needed to solve them under specified computational models. Algorithm complexity and problem complexity are related but distinct: showing that one algorithm is slow does not prove that every possible algorithm for the problem must be slow.

How it works

First define the input size, such as the number of records, graph vertices or bits in a numerical encoding. Then count relevant operations or storage as a function of that size. Asymptotic notation describes growth while abstracting away some constants and lower-order terms. Worst-case, average-case and amortized analyses answer different questions and should not be mixed casually.
Practical runtime also depends on hardware, implementation, data layout and parallelism. Complexity analysis helps explain scaling, while benchmarks reveal actual behavior in a particular setting. Some algorithms trade memory for time, and some methods provide approximate results to reduce cost. The required output and accuracy must be part of the problem definition.

Three practical examples

• A data team compares an all-pairs matching routine with an indexed approach before expanding from thousands to millions of records.
• A computer-vision engineer evaluates how an image-processing method scales with pixel count, neighborhood size and the number of frames.
• A planning team distinguishes the cost of finding a feasible schedule from the additional effort needed to prove that no better schedule exists.

Think of it this way

Think of organizing a library. Checking each book once grows with the number of books; comparing every book with every other book grows much faster. The analogy is limited because real algorithms can reuse work, exploit indexes or depend strongly on the input's structure. Complexity analysis makes those distinctions explicit rather than relying on an intuitive task description.

Worked example

Suppose method A performs approximately n operations and method B approximately n² operations. At n=1,000, the counts are 1,000 and 1,000,000. At n=10,000, they become 10,000 and 100,000,000. A tenfold input increase multiplies the linear count by ten and the quadratic count by one hundred.
These are operation-count models, not measured seconds. A large constant can make the asymptotically better method slower on small inputs. For example, 1,000n exceeds n² while n is below 1,000. This illustrates why both growth analysis and relevant benchmarks are needed when selecting an implementation.

Illustrative case study

Fictional example: Moss Analytics builds an image-duplicate checker that compares every pair of uploaded images. The prototype works on a small folder but slows sharply as the collection grows. The team estimates pair counts, tests an indexing strategy and measures recall as well as runtime. It documents the cases that require more expensive verification. The decision balances resource use and matching quality; it does not assume that a faster approximate search is automatically an equivalent replacement for exhaustive comparison.

Common misconceptions and mistakes

Big-O notation is not a direct runtime prediction and does not usually state an exact operation count. Polynomial-time algorithms are not always practical, especially with high degrees or large constants. Exponential worst-case complexity does not mean every instance is hard. NP does not mean non-polynomial; it is a class defined through efficient verification in the standard decision-problem setting. More processors can help without changing every underlying scaling issue. Finally, input size must refer to the representation: a numeric value and the number of bits needed to write it are different quantities.

Business use

Businesses should connect complexity questions to expected workload growth and service requirements. Measure memory, latency and throughput on representative data, including difficult cases. Ask whether a proposed method is exact, approximate or limited by a timeout, and whether its quality changes with scale. Evaluate infrastructure costs alongside algorithmic redesign. A useful technical report explains which input dimensions dominate cost and where a method stops meeting requirements, rather than presenting a single impressive benchmark without its operating conditions.

People also ask

Is complexity the same as code length?

No. A short program can perform enormous amounts of work, while a longer implementation may use an efficient algorithm.

Does O(n) mean exactly n seconds?

No. It describes an upper-bound growth pattern under stated assumptions, not a time unit.

Can faster hardware solve a complexity problem?

It may extend the practical range, but rapidly growing resource requirements can still dominate as input size increases.

Check your understanding

Under an n² operation model, what happens when input size doubles?

Answer: The leading operation count becomes approximately four times larger. Actual measured runtime may differ because of constants, hardware effects and other work.

Related terms

• Algorithm
• Combinatorial explosion
• Scalability
• Big-O notation
• time complexity
• space complexity
• approximation algorithm

Learn next

Practice counting loops and pair comparisons, then learn asymptotic notation and the difference between worst-case and measured performance. Study problem classes only after defining input representation and the required kind of solution clearly.

More in Computer vision and multimodal AI

• Complex steerable pyramid - A complex steerable pyramid is a multiscale image representation that separates image structure into orientation-selective bands with complex-valued...
• Compositing equation - The compositing equation describes how foreground color, background color and a mixing value combine into an observed pixel.
• Compressive sensing - Compressive sensing, also called compressed sensing, is a framework for recovering signals from fewer measurements than their full ambient dimension by...
• Computational imaging - Computational imaging combines physical measurement and computation to form images or recover scene information.
• Computational photography - Computational photography uses algorithms together with captured light measurements to form, improve, or extend photographic images.
• Computer vision - Computer vision is the field of developing methods that extract useful information from images, video and other visual measurements.

Sources

MIT OpenCourseWare, Lecture 12: Time Complexity: https://ocw.mit.edu/courses/18-404j-theory-of-computation-fall-2020/resources/lecture-12-time-complexity/ Primary university teaching excerpts consulted; full formal and editorial review remain pending. Operation counts and the fictional example are original illustrations.

Previous: Computable Next: Computational graphs