Time complexity

Computers follow steps to finish a job.

We can guess how long a job takes. This depends on how much work there is.

Some jobs are very fast. A computer can find one thing in a list quickly. This is called constant time.

Other jobs take more time. If a list grows, the job takes longer. This is called linear time.

We often look at the worst case. This is the most time a job could take. It helps us plan for big jobs.

Knowing this helps us build better tools. It shows us which jobs are easy or hard.

Computers follow a set of steps to finish a job. This set of steps is called an algorithm.

We want to know how much time an algorithm takes. We call this time complexity. It is hard to guess the exact time. Instead, we count the number of simple steps. We assume each step takes a fixed amount of time.

Sometimes, the same job takes different times. This happens if the input is different. To be safe, we often look at the worst-case. This is the most time a job could take. We also look at the average-case. This is the middle ground for all possible inputs.

We use a special way to write this. It is called big O notation. It shows how the time changes as the input gets bigger.

Some jobs are very fast. Constant time means the time stays the same. It does not matter if the input is big or small.

Other jobs change with the input. Linear time means the time grows at a steady rate. If the input doubles, the time also doubles.

There are many other ways to measure speed. Some jobs take logarithmic time. This is very efficient. The work grows slowly even as the input gets large.

Computers follow sets of steps to finish a job. These steps are called algorithms. Scientists want to know how much time an algorithm takes to run. This idea is called time complexity.

It is hard to guess the exact seconds a computer uses. Instead, we count the number of elementary operations. These are the tiny, simple steps the computer performs. We assume every single step takes a fixed amount of time. This helps us see how the work grows as the task gets bigger.

Sometimes, one job can take different amounts of time. This happens because different inputs can be harder than others. To be safe, we often look at the worst-case time complexity. This tells us the maximum time needed for a certain input size. We can also look at the average-case complexity. This is the average time for all possible inputs of that size. Scientists focus on how time changes as the input size increases. This is called asymptotic behavior.

We use a special math tool called big O notation to describe this. It uses a letter, usually O, followed by a function. The variable n represents the size of the input. For example, n might be the number of bits used. This notation helps us group algorithms into different speed classes. Some jobs are very fast and use constant time. This means the time does not depend on the input size. An example is finding the first item in a sorted list.

Other algorithms take more time as the input grows. Linear time, or O(n), grows at a steady rate. If you double the input, the work also doubles. A linear search is a good example of this. Logarithmic time, or O(log n), is even faster and very efficient. You can see this in a binary search. In a binary search, you look at the middle of a sorted list. You then throw away the half you do not need. This makes the search space get smaller very quickly.

There are many other ways to classify these speeds. Some algorithms take quadratic time, written as O(n²). This includes simple sorting methods like bubble sort. Other tasks take polynomial time, which is written as O(nᵏ). Scientists often call these polynomial time tasks "tractable" or "feasible." This means they are practical to solve. Some very hard problems take exponential time, or O(2ⁿ). These take a huge amount of time as the input grows. Understanding these different speeds helps us choose the best way to solve a problem.

In theoretical computer science, time complexity is a way to describe computational complexity. It measures how much computer time an algorithm needs to finish a task. Because exact seconds are hard to measure, scientists count elementary operations instead. An elementary operation is a simple, basic step performed by a computer. We assume each of these steps takes a fixed amount of time. This allows us to relate the total time to the number of operations performed.

An algorithm's running time can change depending on the specific input it receives. For example, a list might be already sorted or completely scrambled. Because of this variation, researchers often focus on worst-case time complexity. This represents the maximum amount of time required for any input of a certain size. Another method is average-case complexity, which calculates the average time for all possible inputs of a given size. Since there are a finite number of inputs for any size, this average is possible to determine.

To describe these speeds, scientists study asymptotic behavior. This means they look at how the time requirement changes as the input size increases. For small inputs, the exact time might not matter very much. However, as the input size grows, the way the time grows becomes very important. We use big O notation to express this relationship. In this notation, we use the letter O followed by a function of n. Here, n represents the size of the input, such as the number of bits used to represent it.

Algorithms are classified into different complexity classes based on their big O notation. Constant time, written as O(1), is the fastest type. In constant time, the time required is bounded by a value that does not depend on the input size. For instance, accessing a single element in an array takes constant time. Similarly, finding the minimum value in a list that is already sorted in ascending order is O(1). Even if the task takes a bit of time, it remains constant if an upper bound exists that stays the same regardless of n.

Logarithmic time, or O(log n), is another highly efficient class. This occurs when the ratio of operations to input size decreases toward zero as n increases. A classic example is a binary search. In a dictionary search, you might look at the middle entry first. If your word comes earlier, you discard the right half and repeat the process on the left half. This repeatedly halves the search space, making the process very fast. Polylogarithmic time, written as O(log^k n), is a slightly different class used for more complex tasks.

Linear time, or O(n), means the running time increases at a steady rate relative to the input. If you have to read every single item in a list once, you are likely performing a linear time operation. This is the best possible speed for any algorithm that must sequentially read its entire input. Examples include linear search and Kadane's algorithm. Quasilinear time, also called linearithmic time, is written as O(n log n). This is slightly slower than linear time but much faster than quadratic time. Common examples include the Fast Fourier transform and several efficient sorting algorithms like merge sort and heapsort.

As algorithms become more complex, they may fall into polynomial or exponential classes. Polynomial time, or O(n^k), means the time is bounded by a polynomial expression. Problems that can be solved in polynomial time are called tractable or feasible. This class is central to computational complexity theory and includes the class P. In contrast, exponential time, such as O(2^n), grows extremely quickly. Solving the traveling salesman problem via brute-force search is an example of an exponential time task. Other even slower classes include factorial time and double exponential time, which are used for very difficult problems like finding winning strategies in certain board games.