What is n^k? n is any number, right? So then what is k and why is it relevant in terms of polynomial and superpolynomial time?

Yes, k is any positive integer. The difference between n^k and k^n is best understood by noting that "n" is the input size. Putting the input in the exponent (for super polynomial) creates exponential growth. In contrast, polynomial growth puts a fixed k in the exponent. Hope that helps!

Do I need to attend a college-level Algorithms course if my goal is to become a web developer? Or it isn't necessary for beginning a career in this field?

It's not generally necessary, no. If your goal is to become a web developer, I would concentrate on learning web development skills and developing a portfolio of projects, like creating apps for hackathons or websites for local non-profits. You may find that you will be asked algorithm questions during an interview, but that is highly dependent on the company. For frontend development, I find that practical performance concerns come up more often than algorithmic complexity concerns (but those concerns do intertwine! ). If you do find the time to learn more algorithms: My friend Bianca teaches algorithms and data structures for JavaScript developers on the website Frontend Masters, that might be something to explore as a way to learn those topics. You can also learn some of that here, in our other Algorithms course, under the Computer Science section.

Main content

Course: AP®︎/College Computer Science Principles > Unit 4

Lesson 2: Evaluating algorithms

Categorizing run time efficiency

Google Classroom

It's important to understand the run time efficiency of the algorithms we use. When a computer takes too long to solve a problem, it costs more money and deprives the computer of time to spend on other valuable problems. Plus, if the algorithm is used inside a user-facing app, it may result in frustrated users who give up on the app entirely.

Categorizing run times

We can categorize the run time of an algorithm according to how the number of steps increases as the input size increases. Does it always take the same amount of time? That's a constant increase, a very fast run time. Does it always require looking at every possible permutation of the input? That's an exponential increase, a very slow run time. Most run times are somewhere between.

Constant time

When an algorithm runs in constant time, it means that it always takes a fixed number of steps, no matter how large the input size increases.

As an example, consider accessing the first element of a list:

firstPost ← posts[1]

Even if the list grows to be a million items long, that operation will always require a single step.

We can visualize that relationship as a table:

List size	Steps
1	1
10	1
100	1
1000	1

We can also visualize it as a graph:

A constant run time is ideal, but is typically not possible for algorithms that process multiple pieces of data.

Logarithmic time

When an algorithm runs in logarithmic time, it increases proportionally to the logarithm of the input size.

The binary search algorithm is an algorithm that runs in logarithmic time. Read the measuring efficiency article for a longer explanation of the algorithm.

Here's the pseudocode:

PROCEDURE searchList(numbers, targetNumber) {
  minIndex ← 1
  maxIndex ← LENGTH(numbers)
  REPEAT UNTIL (minIndex > maxIndex) {
    middleIndex ← FLOOR((minIndex+maxIndex)/2)
    IF (targetNumber = numbers[middleIndex]) {
      RETURN middleIndex
    } ELSE {
       IF (targetNumber > numbers[middleIndex]) {
         minIndex ← middleIndex + 1
       } ELSE {
         maxIndex ← middleIndex - 1
       }
     }
  }
  RETURN -1
}

The algorithm uses a loop to look at multiple items in the list, but crucially, it does not look at every item in the list. Specifically, it looks at

\log_{2} n

items, where

n

is the number of items in the list.

We can visualize that relationship in a table:

List size	Steps
1	1
10	4
100	7
1000	10

We can also see that as a graph:

The number of steps is definitely increasing as input size increases, but at a very slow rate.

Linear time

When an algorithm grows in linear time, its number of steps increases in direct proportion to the input size.

The aptly-named linear search algorithm runs in linear time.

The pseudocode shows its simplicity compared to binary search:

PROCEDURE searchList(numbers, targetNumber) {
  index ← 1
  REPEAT UNTIL (index > LENGTH(numbers)) {
    IF (numbers[index] = targetNumber) {
      RETURN index
    }
    index ← index + 1
  }
  RETURN -1
}

This time, the loop looks at every item in the list. This exhaustive search is necessary to search for items in an unsorted list, since there's no way to narrow down where a particular item might be. This algorithm will always require at least as many steps as items in the list.

We can see that in table form:

List size	Steps
1	1
10	10
100	100
1000	1000

Or as a graph:

Quadratic time

When an algorithm grows in quadratic time, its steps increase in proportion to the input size squared.

Several list sorting algorithms run in quadratic time, like selection sort. That algorithm starts from the front of the list, then keeps finding the next smallest value in the list and swapping it with the current value.

Here's pseudocode for selection sort:

i ← 1
REPEAT UNTIL (i > LENGTH(numbers)) {
  minIndex ← i
  j ← i + 1
  // Find next smallest value
  REPEAT UNTIL (j > LENGTH(numbers)) {
    IF (numbers[j] < numbers[minIndex]) {
      minIndex ← j
    }
    j ← j + 1
  }
  // Swap if new minimum found
  IF (minIndex != i) {
    tempNum ← numbers[minIndex]
    numbers[minIndex] ← numbers[i]
    numbers[i] ← tempNum
  }
  i ← i + 1
}

The important thing to notice about the algorithm is the nested loop: it loops through each items in the list, and loops again through the remaining items for each of those items. In this case, the algorithm ends up looking at

\frac{1}{2} (n^{2} - n)

values, where

n

is the number of items in the list.

This table shows how many items it'd examine for lists of increasing sizes:

List size	Steps
1	1
10	45
100	4950
1000	499500

Here's what that looks like in graph form:

Both the table and the graph show that the number of steps for this algorithm increases at a much faster rate than the previous ones.

Exponential time

When an algorithm grows in superpolynomial time, its number of steps increases faster than a polynomial function of the input size.

An algorithm often requires superpolynomial time when it must look at every permutation of values. For example, consider an algorithm that generates all possible numerical passwords for a given password length.

For a password length of 2, it generates 100 passwords:

00 01 02 03 04 05 06 07 08 09
10 11 12 13 14 15 16 17 18 19
20 21 22 23 24 25 26 27 28 29 
30 31 32 33 34 35 36 37 38 39
40 41 42 43 44 45 46 47 48 49
50 51 52 53 54 55 56 57 58 59  
60 61 62 63 64 65 66 67 68 69  
70 71 72 73 74 75 76 77 78 79  
80 81 82 83 84 85 86 87 88 89  
90 91 92 93 94 95 96 97 98 99

That algorithm requires at least

10^{2}

steps, since there are

10

possibilities for each digit (

0

9

) and it must try out every possibility for each of the

2

digits.

For any given password length of

n

, the algorithm requires

10^{n}

steps. That run time increases incredibly quickly, since each additional digit requires 10 times the number of steps.

This table shows how fast that grows for just the first 5 digits:

Digits	Steps
1	10
2	100
3	1000
4	10000
5	100000

Here's what that looks like as a graph:

All together now

Now that we've seen examples of possible run times for algorithms, let's compare them on a graph:

That graph makes it even more clear that there's a definite difference in these run times, especially as input size increases. Since modern computer programs increasingly deal with large data sets (like from millions of users or sensors), the run time efficiency matters quite a bit.

Polynomial vs. superpolynomial

Computer scientists often classify run times into two classes:

Polynomial time describes any run time that does not increase faster than $n^{k}$ ‍, which includes constant time ( $n^{0}$ ‍), logarithmic time ( $\log_{2} n$ ‍), linear time ( $n^{1}$ ‍), quadratic time ( $n^{2}$ ‍), and other higher degree polynomials (like $n^{3}$ ‍).
Superpolynomial time describes any run time that does increase faster than $n^{k}$ ‍, and includes exponential time ( $2^{n}$ ‍), factorial time ( $n!$ ‍), and anything else faster.

Why do we make the split between polynomial and superpolynomial?

This table of run times illustrates why:

	$10$ ‍	$50$ ‍	$100$ ‍	$300$ ‍	$1000$ ‍
$5 n$ ‍	$50$ ‍	$250$ ‍	$500$ ‍	$1500$ ‍	$5000$ ‍
$n^{2}$ ‍	$100$ ‍	$2500$ ‍	$10000$ ‍	$90000$ ‍	$\begin{aligned} 1 million \\ (7 digits) \end{aligned}$ ‍
$n^{3}$ ‍	$1000$ ‍	$125000$ ‍	$\begin{aligned} 1 million \\ (7 digits) \end{aligned}$ ‍	$\begin{aligned} 27 million \\ (8 digits) \end{aligned}$ ‍	$\begin{aligned} 1 billion \\ (10 digits) \end{aligned}$ ‍
$2^{n}$ ‍	$1024$ ‍	$\begin{aligned} 16-digit \\ number \end{aligned}$ ‍	$\begin{aligned} 31-digit \\ number \end{aligned}$ ‍	$\begin{aligned} 91-digit \\ number \end{aligned}$ ‍	$\begin{aligned} 302-digit \\ number \end{aligned}$ ‍
$n!$ ‍	$\begin{aligned} 3.6 million \\ (7 digits) \end{aligned}$ ‍	$\begin{aligned} 65-digit \\ number \end{aligned}$ ‍	$\begin{aligned} 161-digit \\ number \end{aligned}$ ‍	$\begin{aligned} 623-digit \\ number \end{aligned}$ ‍	$\begin{aligned} unimaginably \\ large \end{aligned}$ ‍

Those numbers have no units, so an

n!

algorithm may run in 3.6 million nanoseconds for an

n

of 10, which is less than a second. For an

n

of 50, it'd run in

3 \times 10^{64}

nanoseconds—but there have only been

10^{26}

nanoseconds since the Big Bang! A superpolynomial run time often requires more time than available in the universe, even for relatively small input sizes.

This is why we think of polynomial run times as reasonable and superpolynomial times as unreasonable. A polynomial run time isn't always ideal (and we often try to improve those times), but it is at least feasible.

Computer scientists concentrate their efforts on finding polynomial time algorithms for the problems that currently require superpolynomial time, since that's where the difference matters the most.

Further learning

"Asymptotic analysis" is a more formal method for analyzing algorithmic efficiency. That's not covered here, but if you're interested, you can learn more about Asymptotic analysis from our college-level Algorithms course.

🙋🏽🙋🏻‍♀️🙋🏿‍♂️Do you have any questions about this topic? We'd love to answer—just ask in the questions area below!

Want to join the conversation?

Sort by:

26issaca
Posted a year ago. Direct link to 26issaca's post “I literally cannot unders...”
I literally cannot understand these massive blocks of words
Button navigates to signup pageComment on 26issaca's post “I literally cannot unders...”
(45 votes)
Answer
Joshua
Posted 5 years ago. Direct link to Joshua's post “I tried to _manually_ imp...”
I tried to manually implement selection sort with [2, 8, 5, 3, 9, 4, 1] using notepad while keeping track of the variable values. When I arrived at -
'''REPEAT UNTIL (j > LENGTH(numbers)) {
IF (numbers[j] < numbers[minIndex]) {
minIndex ← j
}'''
, I realized that this loop has no expression that increments 'j' so I presumed that it will infinitely run by that loop. Then, I stopped evaluating the algorithm and just scanned over the following lines of code. In the block -
'''IF (minIndex != i) {
tempNum ← numbers[minIndex]
numbers[i] ← tempNum
numbers[minIndex] <- tempNum
}'''
, given that 'tempNum ← numbers[minIndex]', isn't it that 'numbers[minIndex] <- tempNum' will evaluate to 'numbers[minIndex] <- numbers[minIndex]'? I think the values didn't swap correctly. But this is just mere eyeballing of the code and not practically evaluating it. So there's a high chance that I'm actually wrong about my observations, and I'm really sorry if that's the case.
Button navigates to signup pageComment on Joshua's post “I tried to _manually_ imp...”
(13 votes)
Answer
Arthur
Posted 5 years ago. Direct link to Arthur's post “Do I need to attend a col...”
Do I need to attend a college-level Algorithms course if my goal is to become a web developer? Or it isn't necessary for beginning a career in this field?
Button navigates to signup pageButton navigates to signup page
(0 votes)
Answer
- pamela ❤
  Posted 5 years ago. Direct link to pamela ❤'s post “It's not generally necess...”
  It's not generally necessary, no. If your goal is to become a web developer, I would concentrate on learning web development skills and developing a portfolio of projects, like creating apps for hackathons or websites for local non-profits. You may find that you will be asked algorithm questions during an interview, but that is highly dependent on the company. For frontend development, I find that practical performance concerns come up more often than algorithmic complexity concerns (but those concerns do intertwine! ).
  
  If you do find the time to learn more algorithms: My friend Bianca teaches algorithms and data structures for JavaScript developers on the website Frontend Masters, that might be something to explore as a way to learn those topics. You can also learn some of that here, in our other Algorithms course, under the Computer Science section.
  Comment on pamela ❤'s post “It's not generally necess...”
  (17 votes)
layaz7717
Posted 4 years ago. Direct link to layaz7717's post “What is n^k? n is any num...”
What is n^k? n is any number, right? So then what is k and why is it relevant in terms of polynomial and superpolynomial time?
Button navigates to signup pageButton navigates to signup page
(1 vote)
Answer
- Abhishek Shah
  Posted 4 years ago. Direct link to Abhishek Shah's post “Yes, k is any positive in...”
  Yes, k is any positive integer. The difference between n^k and k^n is best understood by noting that "n" is the input size. Putting the input in the exponent (for super polynomial) creates exponential growth. In contrast, polynomial growth puts a fixed k in the exponent.
  
  Hope that helps!
  Button navigates to signup page
  (5 votes)
Johanne Antoine
Posted 5 years ago. Direct link to Johanne Antoine 's post “There is an error for the...”
There is an error for the 100 passwords, from the third row onward, the passwords say 21 to 29.
Button navigates to signup pageButton navigates to signup page
(1 vote)
Answer
- AmericanFuzz
  Posted 10 days ago. Direct link to AmericanFuzz's post “For me, everything shows ...”
  For me, everything shows up just fine. The CSS of the website could be glitching, please try refreshing the page.
  Button navigates to signup page
  (1 vote)
michael.relleum
Posted 3 years ago. Direct link to michael.relleum's post “The paragraph for Linear ...”
The paragraph for Linear Time states "This algorithm will always require at least as many steps as items in the list." Shouldn't this be "at most" instead of "at least", because more often than not the element will not be at the end of the list and thus be found earlier? Or did I misunderstood that part?
Button navigates to signup pageButton navigates to signup page
(2 votes)
Answer
- KLaudano
  Posted 3 years ago. Direct link to KLaudano's post “You are correct, the algo...”
  You are correct, the algorithm will require at most as many steps as items in the list given that the item will likely be found before the end of the list.
  Button navigates to signup page
  (0 votes)
Iron Programming
Posted 4 years ago. Direct link to Iron Programming's post “When you aren't in the le...”
When you aren't in the lesson page (here), and click on this article, it has a lot of mysterious overflow to the right. Basically, a horizontal scrollbar pops up and allows you to scroll a lot to the right - so I am figuring that you forgot to add overflow-x: hidden; or something like that?
Button navigates to signup pageButton navigates to signup page
(1 vote)
Answer
- Pijus Ran
  Posted 9 months ago. Direct link to Pijus Ran's post “If you look closely at th...”
  If you look closely at the end of the horizontal scroll, you can see a log function. This page was simply poorly designed (mistakes happen)
  Button navigates to signup page
  (1 vote)
jwyayj
Posted a year ago. Direct link to jwyayj's post “For the Quadratic time se...”
For the Quadratic time selection sort pseudocode example, I don't see any incremental increase for i or j. Wouldn't that mean that the algorithm wouldn't work properly? Otherwise I'm not sure what I'm missing.
Button navigates to signup pageButton navigates to signup page
(1 vote)
Answer
luke.wang
Posted a month ago. Direct link to luke.wang's post “For the linear search alg...”
For the linear search algorithm, it should require half as many steps as the list. Isn't that the average of where most target numbers would be located? Or are we assuming the target number is always the last one?
Button navigates to signup pageButton navigates to signup page
(1 vote)
Answer
Jeronimo
Posted 6 months ago. Direct link to Jeronimo's post “Here's pseudocode for sel...”
Here's pseudocode for selection sort:
1. When we swap first we must wright """numbers[minIndex] <- tempNum""" and only then """numbers[i] ← tempNum"""
IF (minIndex != i) {
tempNum ← numbers[minIndex]
numbers[i] ← tempNum
numbers[minIndex] <- tempNum
2. And there also must be j++ and i++ in each "repeat" loop
Am i not right?
Button navigates to signup pageButton navigates to signup page
(1 vote)
Answer