3

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)?

  • I have read many times that -- Citation please. – Robert Harvey Aug 30 '13 at 17:30
  • 3
    @RobertHarvey Introduction to Algorithms 3rd Edition - CLRS (ISBN-978-81-203-4007-7) Page 149. Other than that I'll have to look up. I have read that on this website – Aseem Bansal Aug 30 '13 at 17:34
11

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.

  • So looking at a code how can I tell if it has small m. Among insertion sort, bubble sort and selection sort insertion sort is said to have the smallest constant factor i.e. the m that you said. I have selection sort, bubble sort, insertion sort. How can I tell by looking at these codes which will have small m? – Aseem Bansal Aug 30 '13 at 17:50
  • 9
    Software developers are notoriously bad at estimating how long it will take code to execute by just looking at it. If you really want to know how fast code runs, you measure it, with a profiler or a timer. However, you can get a fair idea how long something takes by how much data it moves around. Sorting a linked list is different from sorting an array, for example, because you're only moving pointers around, not the actual items to be sorted. The comparison algorithm matters too; how long it takes to compare one item with another. – Robert Harvey Aug 30 '13 at 17:51
4

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;
    }
}

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.