Learn how to analyze the runtime of programs using asymptotic notation.

Asymptotic Notation: Conceptual

The first subtype of asymptotic notation we will explore is big Theta (denoted by Θ). We use big Theta when a program has only one case in term of runtime. But what exactly does that mean? Take a look at the pseudocode for a function that prints the values in a list below:

```python3
Function with input that is a list of size N:
 For each value in list:
	Print the value
```

The number of instructions the computer has to perform is based on how many iterations the loop will do because if the loop does more iterations, then the computer will perform instructions. Now, let’s see how many iterations the loop will do dependent on the value of N.

|Size of List| --vs.--|Number of Iterations|
|----|----|----|
|1| |1|
|2||2|
|3||3|
|**.**||**.**|
|**.**||**.**|
|**.**||**.**|
|**.**||**.**|
|**.**||**.**|
|N||N|

As we can see in every case, with a list of size N, the program has a runtime of N because the program has to print a value N times. Thus, we would say the runtime is Θ(N). 

Let’s look at a more complicated example. In the following pseudocode program, the function takes in an integer, N, and counts the number of times it takes for N to be divided by 2 until N reaches 1.
```python3
Function that has integer input N:
	Set a count variable to 0
	Loop while N is not equal to 1:
		Increment count
		N = N/2
	Return count
```
Now, let’s see how many iterations the loop will perform based on N.

|N| --vs.--|Number of Iterations|
|----|----|----|
|1| |0|
|**.**||**.**|
|**.**||**.**|
|**.**||**.**|
|2||1|
|**.**||**.**|
|**.**||**.**|
|**.**||**.**|
|4||2|
|**.**||**.**|
|**.**||**.**|
|**.**||**.**|
|8||3|
|**.**||**.**|
|**.**||**.**|
|**.**||**.**|
|16||4|
|**.**||**.**|
|**.**||**.**|
|**.**||**.**|
|N||log2N|

As we can see, in every case, with an integer N, the loop will iterate log2(N) times. However, because we drop constants in asymptotic notation, we would say that the runtime of this program is Θ(log N).

But what happens when there are multiple runtime cases for a single program? We will learn about that in a future exercise.

Big Theta (Θ)

Before we delve into the multiple runtime cases, let’s see the different common runtimes a program could have. Below is a list of common runtimes that run from fastest to slowest.

- **Θ(1)**. This is _constant_ runtime. This is the runtime when a program will always do the same thing regardless of the input. For instance, a program that only prints “hello, world” runs in `Θ(1)` because the program will always just print “hello, world”.
- **Θ(log N)**. This is _logarithmic_ runtime. You will see this runtime in search algorithms.
- **Θ(N)**. This is _linear_ runtime. You will often see this when you have to iterate through an entire dataset.
- **Θ(N*logN)**. You will see this runtime in sorting algorithms.
- **Θ(N2)**. This is an example of a _polynomial_ runtime. When **N** is raised to the **2nd** power, it's known as a _quadratic_ runtime. You will see this runtime when you have to search through a two-dimensional dataset (like a matrix) or nested loops.
- **Θ(2N)**. This is _exponential_ runtime. You will often see this runtime in recursive algorithms (Don’t worry if you don’t know what that is yet!).
- **Θ(N!)**. This is _factorial_ runtime. You will often see this runtime when you have to generate all of the different permutations of something. For instance, a program that generates all the different ways to order the letters “abcd” would run in this runtime.

Common Runtimes

Sometimes, a program has so much going on that it’s hard to find the runtime of it. Take a look at the pseudocode program that first prints all the positive values up to N and then returns the number of times it takes to divide N by 2 until N is 1.

```
Function that takes a positive integer N:
	Set a variable i equal to 1
	Loop until i is equal to N:
		Print i
		Increment i
	
	Set a count variable to 0
	Loop while N is not equal to 1:
		Increment count
		N = N/2
	Return count
```

Rather than look at this program all at once, let’s divide into two chunks: the first loop and the second loop. 
- In the first loop, we iterate until we reach N. Thus the runtime of the first loop is Θ(N). 
- However, the second loop, as demonstrated in a previous exercise, runs in Θ(log N). 

Now, we can add the runtimes together, so the runtime is Θ(N) + Θ(log N).

However, when analyzing the runtime of a program, we only care about the slowest part of the program, and because Θ(N)  is slower than Θ(log N), we would actually just say the runtime of this program is Θ(N). **It is also appropriate to say the runtime is O(N) because if it runs in Θ(N) for every case, then it also runs in Θ(N) for the worst case. Most of the time people will just use big O notation.**



Adding Runtimes

Cheetahs. Ferraris. Life. All are fast, but how do you know which one is the fastest? You can measure a cheetah’s and a Ferrari’s speed with a speedometer. You can measure life with years and months. 

But what about computer programs? In fact, you _can_ time a computer program, but different computers run at different speeds. For example, a program that takes 12 nanoseconds on one computer could take 45 milliseconds on another. Therefore, we need a more general way to gauge a program’s runtime. We do this with _Asymptotic Notation_.

Instead of timing a program, through asymptotic notation, we can calculate a program’s runtime by looking at how many instructions the computer has to perform based on the size of the program’s input: N.

For instance, a program that has input of size N may tell the computer to run 5N2+3N+2 instructions. (We will get into how we get this kind of expression in future exercises.) Nevertheless, this is still a fairly messy and large expression. For asymptotic notation, we drop all of our constants (the numbers) because as N becomes extremely large, the constants will make minute differences. After changing our constants, we have N2+N. If we take each of these terms in the expression and graph them, we see that the N2 term grows faster than the N term. 

![alt text](https://content.codecademy.com/programs/cs-path/asymptotic%20notation/conceptual/runtimes%20compare.png)


For example, when N is 1000:
- the N2 term is 1,000,000
- the N term is 1,000

As you can see, the N2 term is much more significant than the N term. When N is larger than 1000, the difference becomes even more significant. Because the difference is so enormous, we don’t even need to consider the N term when calculating the runtime. Thus, for this program, we would describe the runtime in terms of N2. There are three different ways we could describe the runtime of this program: big Theta or Θ(N2), big O or O(N2), big Omega or Ω(N2). The difference between the three and when to use which one will be detailed in the next exercises.

You may see the term **execution count** used in evaluating algorithms. Execution count is more precise than Big O notation. The following method, `addUpTo()`, depending on how we count the number of operations, can be as low as 2N or as high as 5N + 2 

```java
public class Main() { 
 void int addUpTo(int n) {
 int total = 0;
 for (int i = 1; i <= n; i++) {
 total += i;
 }
 return total;
 } 
}
```

Determining execution count can increase in difficulty as our algorithms become even more sophisticated! 

But regardless of the execution count, the number of operations grows roughly proportionally with n. If n doubles, the number of operations will also roughly double. 

Big O Notation is a way to formalize fuzzy counting. It allows us to talk formally about how the runtime of an algorithm grows as the inputs grow. As we will see, Big O doesn’t focus on the details, only the trends

What is Asymptotic Notation?

Let’s review what we learned:
- We use asymptotic notation to describe the runtime of a program. The three types of asymptotic notation are big Theta, big Omega, and big O.
- We use big Theta (Θ) to describe the runtime if the runtime of the program is the same in every case.
- The different common runtimes from fastest to slowest are: Θ(1), Θ(log N), Θ(N), Θ(N log N), Θ(N2), Θ(2N), Θ(N!).
- We use big Omega (Ω) to describe the best-case running time of a program.
- We use big O (O) to describe the worst-case running time of a program.
- **We typically describe a program’s running time in terms of big O.**
- When finding the runtime of a program with multiple steps, you can divide the program into different sections and add the runtimes of the various sections. You can then take the slowest runtime and use that runtime to describe the entire program.
- When analyzing the runtime of a program, we care about which part of the program is the slowest.

Now that we conceptually understand what asymptotic notation is, let’s practice analyzing and improving runtimes with real programming language examples!

Review

Sometimes, a program may have a different runtime for the best case and worst case. For instance, a program could have a best case runtime of Θ(1) and a worst case of Θ(N). We use a different notation when this is the case. We use big Omega or Ω to describe the best case and big O or O to describe the worst case. Take a look at the following pseudocode that returns True if 12 is in the list and False otherwise:

```python3
Function with input that is a list of size N:
	For each value in the list:
		If value is equal to 12:
			Return True
	Return False
```
How many times will the loop iterate? Let’s take a list of size 1000. If the first value in the list was 12, then the loop would only iterate once. However,  if 12 wasn’t in the list at all, the loop would iterate 1000 times. If the input was a list of size N, the loop could iterate anywhere from 1 to N times depending on where 12 is in the list (or if it’s in the list at all). Thus, in the best case, it has a constant runtime and in the worst case it has a linear runtime. 

There are many ways we could describe the runtime of this program:
- This program has a best case runtime of Θ(1).
- This program has a worst case runtime of Θ(N).
- This program has a runtime of Ω(1).
- This program has a runtime O(N).

You may be tempted to say the following:
- This program has a runtime of Θ(N).

However, this is not true because the program does not have a linear runtime in every case, only the worst case.

In fact, when describing runtime, people typically discuss the worst case because you should always prepare for the worst case scenario! **Often times, in technical interviews, they will only ask you for the big O of a program.**

Great! Now you know the different types of asymptotic notation and when to use which one! Now, let's delve into more complex program runtimes!

