CODEWITHSUNDEEP
algorithmperformance
Yuan Wen
Yuan Wen

Reputation: 1711

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

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.

Upvotes: 3

Views: 1646

Answers (2)

Albert
Albert

Reputation: 29

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!

Upvotes: 2

Salvador Dali
Salvador Dali

Reputation: 222761

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.

Upvotes: 6

Related Questions