Overview:

Algorithms are the heart and soul of computer science. They are step-by-step instructions that computers follow to solve problems. But have you ever wondered how computer scientists measure and compare the efficiency of these algorithms? In the fast-paced world of computer science and problem-solving, algorithms play a pivotal role. They are the building blocks of efficient and intelligent software, powering everything from search engines to recommendation systems. Here we will dive deep into the fascinating world of algorithm design and analysis, exploring key concepts, strategies, and their real-world applications.

What is meant by Algorithm Analysis?

As we all know that algorithm is a sequence of well-defined actions that a computer/person can follow to achieve a desired result. Algorithm analysis is an important part of computational complexity theory, which provides theoretical estimation for the required resources of an algorithm to solve a specific computational problem. Analysis of algorithms is the determination of the amount of time and space resources required to execute in. It involves assessing how an algorithm behaves in terms of time and space efficiency as the size of the input data increases.

In simpler terms we can say that : Algorithm analysis is like evaluating how fast and how much memory a recipe takes to make a meal. Imagine you have two recipes for making sandwich, and you want to know which one is quicker and needs less space in your kitchen.

• Time Complexity is like checking which recipe takes less time to make the sandwich. For example, Recipe A might take 5 minutes, while Recipe B might take 15 minutes. So, Recipe A is faster.
• Space Complexity is like figuring out which recipe needs less space in your kitchen counter. If Recipe A needs just a small plate, and a knife, but Recipe B requires a big cutting board, multiple bowls, and more space, then Recipe A needs less space.

What is the need for Analysis of the Algorithm ?

Imagine you have a recipe to make your favorite dish. This recipe is like an algorithm for cooking that dish. You follow the steps in the recipe to get the desired result – a delicious meal.  

Now, think about this: What if you could make your meal faster, user fewer ingrediants, or make it taste even better? To do that, you need ot analyze your cooking process, just like we analyze algorithms.

Here's why we need to analyze algorithms:

Efficiency: We want to find the best way to solve a problem with the least amount of time and resources, just like finding the quickest and easiest way to cook your meal. Analyzing algorithms helps us figure out which one is the most efficient.

Scalability: Some recipes may work well for cooking a small portion, but what if you have to make a big meal for a party? Similarly, some algorithms may work fine for small datasets, but they might slow down or become impractical when dealing with huge amounts of data. Algorithm analysis helps us understand how well an algorithm can scale up.

Optimization: You might want to adjust the recipe by adding or removing ingredients to make your meal taste better. Similarly, we can tweak algorithms to make them better suited for specific tasks or to improve their performance.

Comparisons: Just as you might compare different recipes to see which one you like the most, we compare algorithms to determine which one is the most suitable for a particular problem.

In essence, analyzing algorithms is like looking at recipes for solving problems in the most efficient, practical, and optimized way. 

What are Asymptotic Notations ?

Asymptotic notations are a set of mathematical notations used in computer science and mathematics to describe the behavior of functions, particularly in the context of analyzing algorithms. They help us express how the performance or efficiency of an algorithm or function changes as its input size grows towards infinity. These notations are used to compare and analyze algorithms without getting into precise, minute details.

Types of Asymptotic notations:

Thera are mainly three asymptotic notations:

• Big-O notation
• Omega notation
• Theta notation

Big-O Notation (O-notations)

This notations describes the upper bound or worst-case behavior of an algorithm. It gives an upper limit on how long an algorithm will take to run, expressed as a function of input size. For example, if an algorithm is O(n^2), it means the algorithm's runtime will grow no faster than the square of the input size.

Since it gives the worst-case running time of an algorithm (i.e., maximum time required by algorithm for all input values), it is widely used to analyze an algorithm as we are always interested in the worst-case scenario.

Let us take the example of the linear search to calculate the best time complexity. Suppose, you have an array of numbers and you to search for a number.

Code:

int linear_search(int arr, int l, int target) {
    int i;
    for (i = 0; i < l; i++) {
        if (arr[i] == target) {
            return arr[i]
        }
    }
    return -1
}
 

Now Suppose, the element we are trying to find is at the end of the array. So, we will have to traverse the whole array before finding the element. Hence, we can say that the worst case for this algorithm is O(N) itself. Because we have to go through at most N elements before finding our target. So, this is how we calculate the worst case of the algorithms.

Omega Notation (Ω-notation)

Omega notation represents the lower bound or best-case behavior of an algorithm. It provides a lower limit on the runtime of an algorithm as a function of the input size. For instance, if an algorithm is Ω(n), it means the algorithm will take at least linear time. i.e., algorithm will take a minimum of N time to run, it can never take sometime less than that. It is represented in terms of Big Omega ($\Omega$ ) notation.

Example:

If an algorithm has a runtime of $\Omega$ (n), it means that its performance will not be better than linear time as the input size grows. In other words, it has a lower bound of linear time complexity.

Let us take our previous example where we were performing the linear search. Now suppose, the number you are searching for is present at the very beginning index of the array. In that case, your algorithm will take O(1) time to find the number in the best case. So, the best case complexity for this algorithm becomes O(1), and you will get your output at a constant time.

Theta Notation (Θ-notation)

Theta notation combines both the upper and lower bounds to describe the tightest possible bound on an algorithm`s runtime. It defines the exact behavior of an algorithm. It is used for analyzing the average-case complexity of an algorithm.

Example:

If an algorithm has a runtime of (n log n), it means that its performance grows at the rate as n log n, neither faster, nor slower. This notation is commonly used to represent average -case time complexity.

In our previous example, suppose we need to find any element which is present in the mid of our array. So, for that, we need to traverse at least the half length of the array. In other words, it will take us O(n/2) time for us to traverse the half-length. The time complexity O(n/2) is as good as O(n). That is why we say that the average case in most of the cases depicts the worst case of an algorithm.