🅾️Big O

What is Big O Notation?

Big O notation 📏 is used to describe the efficiency 🚀 of algorithms 🤖. It represents the upper bound 🔼 on the runtime ⏱️ or space complexity 📦 of an algorithm as the input size 📊 grows large.

1. Time complexity: ⏱️ It measures how the running time of an algorithm increases with the size of the input.

2. Space complexity: 🧠 It measures the amount of additional memory space required by an algorithm to solve a problem.

3. Asymptotic analysis: 📊 Big O notation simplifies the analysis by considering the dominant term with the highest growth rate and ignoring constant factors.

4. O(1) - Constant time: ⏲️ Algorithms with constant time complexity have a consistent running time regardless of the input size.

5. O(log n) - Logarithmic time: 🔍 Algorithms with logarithmic time complexity have running times that increase slowly as the input size grows.

6. O(n) - Linear time: 🚶 Algorithms with linear time complexity have running times directly proportional to the input size.

7. O(n log n) - Linearithmic time: 📈🔍 Algorithms with linearithmic time complexity have running times that are slightly higher than linear time but still grow efficiently.

8. O(n^2) - Quadratic time: 🚀 Algorithms with quadratic time complexity have running times that increase with the square of the input size.

9. O(2^n) - Exponential time: 🚀🚀 Algorithms with exponential time complexity have running times that grow exponentially with the input size.

10. O(n!) - Factorial time: 🚀🚀🚀 Algorithms with factorial time complexity have running times that grow factorially with the input size.

11. Best case, worst case, and average case: ⬆️⬇️🔃 Big O notation represents the worst-case scenario of an algorithm. Best and average cases are also important to consider.

12. Algorithmic efficiency: 💪 Big O notation provides a way to compare the efficiency of different algorithms.

13. Time complexity analysis: ⏱️🔍 To determine the time complexity of an algorithm, analyze how operations' frequency or execution time scales with the input size.

14. Space complexity analysis: 🧠🔍 To determine the space complexity of an algorithm, consider the additional memory required and how it scales with the input size.

Big O notation rules: 📝

When analyzing the time complexity of an algorithm using Big O notation, we can apply certain rules to simplify and focus on the most significant aspects. Here are two important rules to keep in mind:

1. Dropping Constants 🚫

   • When analyzing the time complexity, we can drop the constant factors.

   • Example:

     • O(3n) can be simplified to O(n)

     • O(2n^2) can be simplified to O(n^2)

   • The reason for dropping constants is that as the input size grows larger, the impact of constant factors becomes less significant.

2. Focusing on the Most Significant Term 👀

   • In many cases, an algorithm's time complexity is determined by the most significant term.

   • Example:

     • If an algorithm has a time complexity of O(n^2 + n), we focus on the term with the highest power, which is n^2. Thus, the time complexity is O(n^2).

     • If an algorithm has a time complexity of O(5n^3 + 10n^2), we focus on the term with the highest power, which is n^3. Thus, the time complexity is O(n^3).

   • By focusing on the most significant term, we capture the dominant factor that influences the growth rate of the algorithm as the input size increases.

Different time complexities with for-loop examples

O(1) Constant Time ⏰

• The runtime or space requirements of the algorithm remain constant, regardless of the input size.

• Example:

for (int i = 0; i < 10; i++) {
    // Code that takes a constant amount of time or space
}

🚀 This loop will always execute exactly 10 times, regardless of the input size.

O(log n) Logarithmic Time ⏳

• The runtime or space requirements grow logarithmically as the input size increases.

• Example:

for (int i = 1; i < n; i *= 2) {
    // Code that takes a constant amount of time or space
}

🔍 This loop doubles the value of i in each iteration. It will execute approximately log n times.

O(n) Linear Time 🐢

• The runtime or space requirements grow linearly with the input size.

• Example:

for (int i = 0; i < n; i++) {
    // Code that takes a constant amount of time or space
}

🐌 This loop will execute n times, directly proportional to the input size.

O(n^2) Quadratic Time 🐢🐢

• The runtime or space requirements grow quadratically with the input size.

• Example:

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        // Code that takes a constant amount of time or space
    }
}

🐢🐢 This loop nests another loop inside it, resulting in n iterations of the inner loop for each iteration of the outer loop.

Space Complexity

Let's consider a simple Java method that sums up all the numbers in an array:

int sumArray(int[] nums) {
    int sum = 0; // 📦 Variable to store the sum

    for (int num : nums) {
        sum += num;
    }

    return sum;
}

In this code, the space complexity is O(1) because the amount of memory used remains constant, regardless of the input size. The only memory required is for the sum variable, represented by a single 📦 box.

Now, let's consider a different scenario where we create a new array to store the squared values of the input array:

int[] squareArray(int[] nums) {
    int n = nums.length;
    int[] squared = new int[n]; // 📦📦📦 Array to store squared values

    for (int i = 0; i < n; i++) {
        squared[i] = nums[i] * nums[i];
    }

    return squared;
}

In this code, the space complexity is O(n) because the memory required grows linearly with the input size. The array squared requires the same amount of memory as the input array nums, represented by multiple 📦 boxes stacked next to each other.