In "Introduction to Algorithms", what does “tight code” mean？

Question

I'm reading "Introduction to Algorithms",the author refers to "tight code" several times. Does "tight" only means there are lesser code to write to implement one algorithm compared to another?

In the book, the author says that insertion sort and quicksort both have "tight code" which makes the algorithms faster. For example, quicksort is faster than heapsort in general although their time complexity are the same.

Of course, I don't think "tight code" means writing code without proper formatting, extra spaces, blank line.

Have a look here: http://programmers.stackexchange.com/a/210004/216897 — usamazf, Apr 07 '16 at 06:26

score 6 · Accepted Answer · answered Apr 07 '16 at 06:30

6

Tight code means that a constant in time complexity is small. When you speak about the algorithm and tell that it is O(n^2), it means that for a very large numbers it grows quadratically. This can be 1/2*n^2, but it can be 10^7 * n^2 or c * n^2.

So when this c is small it means that the algorithm or the code is tight. Clearly in your algorithm you want it to be as tight as possible.

answered Apr 07 '16 at 06:30

Salvador Dali

214,103
147
703
753

Oh,but if tight only means smaller constant,Why do they say smaller constant directly?Is there anything more than this?@Salvador Dali – Yuan Wen Apr 07 '16 at 06:43
@YuanWen I also think they should have told this exactly. But yes, this only means smaller constant. It has nothing to do with code formatting or how the code is written. – Salvador Dali Apr 07 '16 at 06:56

score 2 · Answer 2 · edited May 23 '17 at 10:28

Quicksort and heapsort both has time complexity of, represented with the big O notation, O(nlogn). What makes Quicksort faster than heapsort in practice is its constant that was ignored by big O analysis. Tightcode refers to that constant.

For example, let's say there is a loop that processes n(a large input) times, and every time it takes k unit time to process. Therefore the total process time will be T(processing time) = k*n (unit time). However, in big O algorithm analysis, we only care about the growth rate of an algorithm (how much does the processing time increases as the input size increases). So, the time complexity of this loop will be O(n), and n stands for a large input size.This way we ignoring k which is a constant that will not grow. So what the book roughly means is that the k of quciksort is smaller than heapsort in practice. If you are interested in why quick sort is faster, where is a link: Quicksort superiority over Heap Sort Good luck!

In "Introduction to Algorithms", what does “tight code” mean？

2 Answers2