Understanding the Complexity of Algorithms

In this article, we are going to discuss about the complexity of algorithms. As I said earlier in real-time we might have a lot of options when choosing an algorithm. This means for a single problem we will have a lot of algorithms to solve.

Analysis of the algorithm helps you to choose the right one. We will analyze the algorithms based on the complexity of the programs. So it’s very important to know how to calculate the complexity of the program.

Complexity of Algorithms

So how to calculate the complexity of the program? In every program arithmetic operations like addition, subtraction. multiplication and division and assigning some value to one variable and all will take one step to execute. So these lines’ complexity enrolls constant time.

String search(int arr[], int x){
        String resultStr = "Value not found";
        for(int i=0; i<arr.length; i++){
            if(arr[i] == x){
                resultStr = "we found it";
            }
        }
        return resultStr;
    }

If you take this program it’s a simple search.

Here, I am searching the value x within this array. If a found the value x. I will be print “we found it”. If the value is not available means I will just print “value not found”.

If I calculate the complexity for this program. This line String resultStr = "Value not found"; will take one step to execute means. This line will execute for only one time. Because just we are assigning some text to this string variable.

So complexity for this line will be constant time. To represent this constant time we will use the alphabet C. So I mentioned it as C0.

The if(arr[i] == x) complexity is also constant time. And String resultStr = "we found it"; this assigning operation also will execute only one time.

So I will represent this as constant i.e C1 and C2. But these lines of code are present inside of your for loop. This means how many times this for loop is executing that these lines of code will also execute. If this for loop executes four n times then these lines also will execute for n times.

Okay, I will calculate the complexity of this problem.

String resultStr = "value not found"; it’s constant and time i.e C0. Plus this if(arr[i] == x) if block is C1. Plus this String resultStr = "we found it"; assigning operation is also constant time so C2. These C1 and C2 are inside of for loop. So, so many times these lines will execute.

In this case, if I am using 10 elements within this array, these two lines of code will execute 10 times. If it’s a thousand elements then it will execute for thousand times.

So I’m referring to this as n times for C1 and C2. Plus this return resultStr; return statement. This is also constant time. So I’m referring to this as C3.

[ C0 + n(C1 + C2) + C3 ]

Finally, this is the expression we got for this program. When calculating the complexity we will take the highest power option as the complexity of the program.

So for this program complexity is n.

Just consider we have this for loop in inside another for loop. So we will write the expression as C0 + n(n(C1 + C2)) + C3. This complete section is inside of another for loop, right? So C0 + n(n(C1 + C2)) + C3 is equal to C0 + n^2(C1 + C2) + C3 . Here, maximum power is 2. For this case complexity is n^2.

This is how we have to calculate the complexity of the algorithms.

nv-author-image

Kalpesh Khairnar

Hello Everyone, I'm Kalpesh. Energetic and passionate college student with the ability to work with open-source technologies. I spend most of my time in programming, blogging and helping other programming geeks.

Leave a Reply

Your email address will not be published. Required fields are marked *