When is a code considered tight and how does it increase efficiency of the code?

Question

I have read many times that insertion sort has tight code and hence the hidden constant factor in its asymptotic complexity is smaller. I just read yesterday that quick sort has tight code just like insertion sort so it also has smaller hidden constant factor. It is one of the reasons it is considered best among the O(n lg n) sorting algorithms.

I don't understand what does it mean when someone says that this algorithm's code is tight. What does that mean exactly and how does it lead to improvement in the efficiency of the algorithm (the smaller hidden constant factor in asymptotic complexity)?

Answer 1

When an algorithm is given a Big O designation such as O(n log n), it tells you how the algorithm will scale; that is, how well will it perform as you increase the size of n to a large number.

Let's say I have an algorithm that is O(n) over a data set. That means that there's a loop in the code somewhere that executes n times, once for each element in the data set. How long will it take to execute? Assuming that each iteration of the loop takes about the same amount of time, it will take

m * n

Where m is the amount of time it takes to process one element of the data set.

It is clear that it will take longer to process the data set if m is higher. Big O doesn't address that time at all; it only states that (in this case), the algorithm will scale linearly as a function of the data set size.

So a "tight loop" is simply one that has a smaller m.

This is the "hidden constant factor" that the book talks about. Reducing m improves efficiency because any improvement in m will be multiplied over the whole data set.

Answer 2

Tight code is source code that is very efficient in that it accomplishes a task with a minimum of resources and no superfluous code.

I want to display the sum of 1 and 3 in C#. Program 1 accomplishes this task with tight code. Program 2 does not.

Program 1:

class Program
{
    static void Main(string[] args)
    {
        Console.Write(4);
    }
}

Program 2:

class Program
{
    static void Main(string[] args)
    {
        var myAdder = new Adder();
        Console.Write(myAdder.GetSum());
    }
}

class Adder
{
    public Adder()
    {
        this.FirstOperand = 1;
        this.SecondOperand = 3;
    }

    public int FirstOperand { get; set; }
    public int SecondOperand { get; set; }

    public int GetSum()
    {
        return this.FirstOperand + this.SecondOperand;
    }
}