## The 4 rules
### - Worst case
```java
List capitals = Arrays.asList("Delhi", "Toronto", "Oslo", "Moscow", "DC", "Paris");
public String findIdealCapital(){
for (String cap:capitals){
if (cap.equals("Toronto")){
return "Capital found"
}
return "Ideal capital not found";
}
}
```
The code snippet above has a runtime complexity of `O(n)` even though `Toronto` is the second item in the list and the loop will quit after it completes the second iteration. Big O always describes worse-case runtimes.
### - Remove constants
```java
while (index < input.length/2){
// Do stuff
}
```
As we see in the above code snippet, the loop loops through only half the number of times. Despite that, the runtime complexity is `O(n)`. We always drop the constants in runtime since Big O notation does not describe absolute values but rather describes a rate of increase. Therefore, O(n) and O(2n) is actually O(n).
Suppose we plot a graph of `# operations` vs `# elements`, a graph of `O(n) vs n` is less steeper than `O(2n) vs n` but this does not matter. What we care about is the fact that the rate of increase is linear.
### - Different terms for inputs
Sometimes, a function has loops that loop through different inputs. In such a case, the runtime complexity will have to use different terms for its inputs. For e.g., the runtime complexity of the function below is `O(a + b)`
```java
void compute(List a1, List a2){
for (Object a:a1){
// Do stuff
}
for (Object a:a2){
// Do stuff
}
}
```
### - Drop non-dominants or insignificant parts
Let us consider an algorithm that is designed to calculate: $45n^3 + 20n^2 + 19$.
If `n = 1`, then `84`
If `n = 2`, then `459`
If `n = 10`, then 47,019
We can see that as and when ānā increases, the significance of the terms `19` and $20n^2$ keeps reducing. The main term is therefore $45n^3$. We drop constants and insignificant terms because Big O analysis is mainly focussed on scenarios when `n` gets arbitrarily large.
A programmatic example:
```java
public void sumNumbers(List numbers){
for (Integer i:numbers) {
System.out.println("Number is" + i);
}
for (Integer i:numbers)
for (Integer j:numbers)
System.out.println("Sum is: " + (i+j))
}
```
The runtime complexity of the above program is `O(n + n^2)` but since we drop the non-dominant parts, the runtime complexity is `O(n^2)`