# Big(O) Notation

### Step 1: Understanding Big O Notation

Big O notation describes how the runtime of an algorithm grows relative to the size of the input (denoted as ( n )) as ( n ) becomes large. It's used to classify algorithms according to their growth rates, which helps in understanding the scalability of the algorithm.

### Step 2: Analyzing the Expression ( O(n^2 + n + 2) )

Given the expression:

\[ O(n^2 + n + 2) \]

This expression represents the time complexity of an algorithm where:

* ( n^2 ) corresponds to some part of the algorithm that takes time proportional to the square of the input size.
    
* ( n ) corresponds to some part of the algorithm that takes time proportional to the input size.
    
* ( 2 ) corresponds to some constant time operations, independent of the input size.
    

### Step 3: Identifying Growth Rates of Each Term

Each term in the expression has a different growth rate as ( n ) increases:

* **( n^2 )**: This is a quadratic term. As ( n ) grows, ( n^2 ) grows much faster than ( n ) or any constant. For example, if ( n = 10 ), then ( n^2 = 100 ), and if ( n = 100 ), then ( n^2 = 10,000 ). The rate of growth is proportional to the square of ( n ).
    
* **( n )**: This is a linear term. It grows proportionally to ( n ). If ( n = 10 ), then ( n = 10 ), and if ( n = 100 ), then ( n = 100 ). The rate of growth is directly proportional to ( n ).
    
* **( 2 )**: This is a constant term. No matter how large ( n ) gets, this term will always remain 2. It does not grow with ( n ) at all.
    

### Step 4: Identifying the Dominant Term

In Big O notation, we are primarily interested in how the algorithm behaves as ( n ) becomes very large (approaches infinity). The term with the highest growth rate will dominate the performance of the algorithm, meaning it will have the greatest impact on the runtime as ( n ) increases.

In the expression ( n^2 + n + 2 ):

* **( n^2 )** dominates because it grows faster than both ( n ) and ( 2 ) as ( n ) increases.
    

### Step 5: Simplifying the Expression

Since ( n^2 ) dominates the other terms, we can simplify the time complexity by ignoring the smaller terms (( n ) and ( 2 )) because their contribution to the overall runtime becomes negligible for large ( n ).

Therefore, the expression simplifies to:

\[ O(n^2) \]

### Step 6: Conclusion

The Big O notation for the time complexity ( O(n^2 + n + 2) ) is **O(n^2)**.

### Summary of the Process:

1. **List all terms in the expression**: ( n^2 ), ( n ), and ( 2 ).
    
2. **Determine the growth rate of each term**:
    
    * ( n^2 ): Quadratic growth.
        
    * ( n ): Linear growth.
        
    * ( 2 ): Constant.
        
3. **Identify the dominant term**: The term with the highest growth rate, which is ( n^2 ) in this case.
    
4. **Simplify by ignoring lower-order terms and constants**: Drop ( n ) and ( 2 ) as they have lower growth rates.
    
5. **Result**: The time complexity in Big O notation is ( O(n^2) ).
    

This means that as the input size ( n ) increases, the algorithm's runtime grows at a rate proportional to ( n^2 ).

Certainly! Let’s explore a few more examples to understand how to determine Big O notation for different time complexity expressions, using some emojis to keep it engaging! 🎉

### Example 1: ( O(3n^3 + 2n^2 + 10n + 5) )

#### Step 1: List All Terms 📝

* ( 3n^3 )
    
* ( 2n^2 )
    
* ( 10n )
    
* ( 5 ) (constant)
    

#### Step 2: Determine Growth Rates 🚀

* **( n^3 )**: Cubic growth, fastest-growing term. 📈
    
* **( n^2 )**: Quadratic growth.
    
* **( n )**: Linear growth.
    
* **( 5 )**: Constant, doesn’t grow with ( n ). 🔢
    

#### Step 3: Identify the Dominant Term 🏆

* **( 3n^3 )** dominates because ( n^3 ) grows faster than the other terms as ( n ) increases.
    

#### Step 4: Simplify ✂️

* Drop the lower-order terms ( 2n^2 ), ( 10n ), and ( 5 ).
    

#### Result ✅

* The time complexity is ( O(n^3) ).
    

### Example 5: ( O(100n + 300) )

#### Step 1: List All Terms 📝

* ( 100n )
    
* ( 300 ) (constant)
    

#### Step 2: Determine Growth Rates 🚀

* **( n )**: Linear growth. ➡️
    
* **( 300 )**: Constant, doesn’t grow with ( n ). 🔢
    

#### Step 3: Identify the Dominant Term 🏆

* **( 100n )** dominates because linear growth increases as ( n ) increases, while the constant ( 300 ) doesn’t change.
    

#### Step 4: Simplify ✂️

* Drop the constant ( 300 ).
    

#### Result ✅

* The time complexity is ( O(n) ).
    

### Summary 🌟

1. **Identify all terms** in the expression. 📝
    
2. **Determine the growth rate** of each term. 🚀
    
3. **Identify the term with the highest growth rate**. 🏆
    
4. **Simplify** by removing lower-order terms and constants. ✂️
    
5. **Result**: The simplified term represents the time complexity in Big O notation. ✅
    

These examples should help you understand how to simplify complex time complexity expressions to their Big O form using different scenarios. 🎉