There are many questions about the performance of commands or scripts on the U+L SE asset. As time is of the essence, this is often evaluated using the bash time reserved word or the external time command and a subset of the target data, under average or no load.Yet there are scenarios which are either about a large number of files or just operations on very big files. In some instances a careful examination of what happens in the shell, intricate knowledge of command behavior, even hardware considerations, provide insight into efficiency. But benchmarking remains no simple affair.In one instance recently a community member made a comment about the time complexity of a command, implying that since there was no sorting operation - and not merely no sort command - it would ultimately scale better with more data. The solution involved awk, whereas another solution involved for instance a combination of the grep, sort and head commands.Is this just an instance of the simpler the better - what are main implications of time complexity when designing shell scripts which operate on huge data sets(number or size)? Beyond common sense and sorting (an operation for which there is a seemingly high level of intuition about performance costs, even for a non expert), is there a well known common time complexity example which would showcase how the concepts apply in practice to shell scripting?
Time complexity implications when designing shell scripts for large data/high number of files?
complexity;time estimation
First you have to understand what the time complexity of a program is telling you. Time complexity is a measure of how the running time of a program changes as the size of the input data changes. If n is the size of the input data, then saying that program A is O(n) and program B is O(n * log n) means that the running time of program A is always less than C * n, and the running time of program B is always less than K * n * log n. C and K are some constants, which we usually don't know.If you graph (C * n)  and (K * n * log n) versus n, there will be some point at which the line for  (K * n * log n) will cross above the line (C * n). That means that for all data sets larger than that point, program A will compute the answer faster than program B. Because we typically don't know what the constants C and K are, we don't know what this threshold is, we just know that it exists.Time complexity is calculated for shell scripts the same way it is for any language. The only difference is that some of the statements are more opaque, and you may have to research their implementation, or make assumptions that they are implemented 'reasonably'. The awk script in the example you linked to is just a 'for' loop that touches each element of the input data exactly once. That means it almost certainly has a time complexity of O(n). I say almost certainly, because it is theoretically possible that awk is doing something bizarre internally that would change the time complexity of the script. If you needed a guarantee, you could look at the awk source code and get a definitive answer. However, awk has been around for forty years and worked on by a lot of competent programers, so it's a pretty reasonable assumption that an awk 'for' loop that touches n items is going to have a time complexity of O(n).On the other hand, it's a well known result from analysis of algorithms that no sort routine can have a time complexity better than O(n * log n). That means that the sort command can be treated as a black box, but we can be sure that its time complexity is worse than O(n log n). That means that if the input data gets big enough, there will be some point in which the awk script overtakes the sort and head script.All of the above discussion is really only relevant if your script needs to handle arbitrarily sized data sets. Shell scripts are often written to carry out 'once only' chores on small data sets. In those cases it may not be worth thinking about a running time analysis. Who cares if the awk script solves the problem 2 seconds faster than the sort and head script if you have to invest 45 minutes in learning awk?**If your job requires you to solve problems like this all the time, then yes, of course you should learn awk, and probably three or four other scripting languages. However, that's more about optimizing your career, then about expediently solving the problem at hand.