# Big O Notation

## Pre-exercise

Let's supose that we have an array of NAMES

These NAMES are not sorted.

We want to find if we have in NAMES somebody whose name is "Claudia"

Construct an algorithm to find this out. You have to output if there is a "Claudia" in NAMES or not.

* If NAMES has 5 names
* If NAMES has 50 names
* If NAMES has 5000 names

Supose that each instruction takes 1 nanosecond to be done. Count how many nanosecons we have to wait for the 3 mentioned cases.

 FOUND = FALSE // flag variable
 loop for I from 0 to (5-1) //length -1 
     if NAMES[I] = "CLAUDIA"
         FOUND = TRUE
     end if
 end loop
 if FOUND = TRUE
     output "We have found a Claudia"
 else 
     output "We haven't found a Claudia"
 end if

Let's count
Line 1: 1
Line 2: 5
Line 3: 5
Line 4: 0-5 // zero if we have 0 Claudias and 5 if all of them are Claudias
Line 7: 1
Line 8-10: 1

Total: 13-18

If we have 50

 FOUND = FALSE // flag variable
 loop for I from 0 to (50-1) //length -1 
     if NAMES[I] = "CLAUDIA"
         FOUND = TRUE
     end if
 end loop
 if FOUND = TRUE
     output "We have found a Claudia"
 else 
     output "We haven't found a Claudia"
 end if

Let's count how many times are they going to be executed each line (in worst case scenario)
Line 1: 1
Line 2: 50
Line 3: 50
Line 4: 0-50 (no claudias or all claudias)
Line 7: 1
Line 8-10: 1

Total: 103 -153

If we have 5000

 FOUND = FALSE // flag variable
 loop for I from 0 to (5000-1) //length -1 
     if NAMES[I] = "CLAUDIA"
         FOUND = TRUE
     end if
 end loop
 if FOUND = TRUE
     output "We have found a Claudia"
 else 
     output "We haven't found a Claudia"
 end if

Let's count how many times are they going to be executed each line (in worst case scenario)
Line 1: 1
Line 2: 5000
Line 3: 5000
Line 4: 0-5000 (no claudias or all claudias)
Line 7: 1
Line 8-10: 1

Total: 10003 -15003

Let's say that we want to access the third element of the array NAMES

Construct an algorithm to output the third name of the array NAMES in the 3 cases and count how many lines are going to be executed.

output NAMES[2]

or

I = 2
output NAMES[I]

If we have 5 names in names

This is only 1 line.

If we have 50 names in NAMES, this is still 1 line executed.
If we have 5000 names in NAMES, this is still 1 line executed.

## Big O Notation

So the Big O notation is a way to describe the complexity of an algorithm (or a process) to the upper bound of it when it grows in some variables.

## Change in the O(n) algorithm

Let's suposse that we have to change all the names of all the elements on the array in the case that we have found a CLAUDIA (we need to make them all be called Mr. Anderson)

FOUND = FALSE // flag variable
 loop for I from 0 to (5000-1) //length -1 
     if NAMES[I] = "CLAUDIA"
         FOUND = TRUE
     end if
 end loop
 if FOUND = TRUE
     loop for J from  to (5000-1)
         NAMES[J] = "Mr. Anderson"
     end loop
 else 
     output "We haven't found a Claudia"
 end if

If we have 5 names in NAMES how many lines are we going to execute?

:::spoiler
Line 1: 1
Line 2: 5
Line 3: 5
Line 4: 0-5
Line 7: 1
Line 8: 0-5
Line 9: 0-5
Line 12: 1-0

Total 13-27
:::

If we have 50 names how many lines are we going to execute?

:::spoiler
Line 1: 1
Line 2: 50
Line 3: 50
Line 4: 0-50
Line 7: 1
Line 8: 0-50
Line 9: 0-50
Line 12: 1-0

Total 103-252
:::

If we have 5 000 names how many lines are we going to execute?

:::spoiler
Line 1: 1
Line 2: 5000
Line 3: 5000
Line 4: 0-5000
Line 7: 1
Line 8: 0-5000
Line 9: 0-5000
Line 12: 1-0

Total 10003-25002
:::

If we have 5 000 000 names how many lines are we going to execute?

:::spoiler
Line 1: 1
Line 2: 5000000
Line 3: 5000000
Line 4: 0-5000000
Line 7: 1
Line 8: 0-5000000
Line 9: 0-5000000
Line 12: 1-0

Total 10000003-25000002
:::

This is linear complexity and is written as O(n)

The previous example of accessing elments of an array is called constant and is written O(k) or O(1)