How 2 lines of code may be inefficient then writing 100 lines.

Introduction

At first glance, the title may seem incorrect but in this article I have broken down why, We have all heard we need to optimize our code to fewer lines to make it more organized, But we need to consider the efficiency of the code as well, It is entirely possible the quick 4 lines of loop may not be as efficient as you may think.

Break-down

Yes, shorter lines of code may seem elegant at first, but when it comes to performance fewer lines of code doesn’t always means faster and efficient code. Lets take this simple analogy to understand further.

Example: Lets say you have a 7 identical diamonds and among them one diamond is lighter than others. You need to identify the lighter diamond in less scans as possible. The first thing that may pop up in mind is, we can take each diamond one by one and test to see which one is lighter, This approach sounds simple and efficient at first glance I mean its a basic looping concept.

# The diamonds we have
int diamonds[9] = {1, 1, 1, 1, 0, 1, 1, 1, 1} # light= 0 and heavy= 1
int lightest;
for (int i = 0; i < 9; i++) {
    if (diamonds[i] > heaviest) {
        lightest= diamonds[i];
        break;
    }
}
return lightest;

In above code the number of iterations that the diamonds will be checked will be at most 9, so in total the code will be executed 9 times considering the worst case. The approach is reasonable and works perfectly fine. But what if there was more efficient approach?

Time Complexity: 0(n) —> Where n is the number of the diamonds

Better Approach

Instead of checking weight of every diamond what if we can simply divide the diamonds into group of three. All the groups A, B and C now will have 3 diamonds each.

Now we can simply, sum the weight of the 3 diamonds of group A at once and compare the weight to the diamonds in group B and group C Doing this we will get three conditions

• If(A==B) —> C will be considered to be the group with lighter diamond

• If (A>B) —> B will be considered to be the group with lighter diamond

• If (A<B) —> A will be considered to be the group with lighter diamond

In all the cases, we can analyze that we are simply filtering 3 diamonds among the 9 so 6 diamonds will be rejected.

int diamonds[9] = {1, 1, 1, 0, 1, 1, 1, 1, 1};

int A = diamonds[0] + diamonds[1] + diamonds[2];
int B = diamonds[3] + diamonds[4] + diamonds[5];
int C = diamonds[6] + diamonds[7] + diamonds[8];

if (A == B)
{
    // lighter diamond is in Group C
    if (diamonds[6] < diamonds[7])
        return diamonds[6];
    else if (diamonds[7] < diamonds[6])
        return diamonds[7];
    else
        return diamonds[8];
}
else if (A < B)
{
    // lighter diamond is in Group A
    if (diamonds[0] < diamonds[1])
        return diamonds[0];
    else if (diamonds[1] < diamonds[0])
        return diamonds[1];
    else
        return diamonds[2];
}
else
{
    // lighter diamond is in Group B
    if (diamonds[3] < diamonds[4])
        return diamonds[3];
    else if (diamonds[4] < diamonds[3])
        return diamonds[4];
    else
        return diamonds[5];
}

Time Complexity: O(1)

Conclusion

At first glance, It may seem the second approach is more of a hassle while it may be true initially but in the first approach the code at worst case will be checking 9 diamonds but in the above implementation the 6 diamonds will be rejected initially making the comparisons to be done with only 3 diamonds so the above code will only execute 2 - 3 lines of code making it more efficient with time complexity of Constant.