I don't think grep -i is exponentially (with respect to the number of characters to be grepped) more costly (time wise) than a normal grep because the run times are not too different.
But theoretically it should be. For example
egrep -i abc *
is equivalent to
egrep "abc|abC|aBc|aBC|Abc|AbC|ABc|ABC" *
How do utilities like grep avoid the exponential time in case insensitive queries? Is there a case insensitive comparison operator that Unix inherently supports that such utilities can use?
An i-match between abC and aBc can easily be done, if abC is transformed to lowercase (once), and every input like aBc is translated to lowercase too. Then normal matching.
But maybe it is done, just by ignoring some bits. 'A' is 65, and 'a' is 97. The difference is 32, a power of 2, so it can easily be masked. Even 'ä' (228) and 'Ä' (196) have a difference of 32, but I'm not sure whether it holds for all characters in extended ASCII.
grep like most regular expression engines translates the pattern that you specify into a deterministic finite-state automaton (DFA).
A common way of expressing case insensitivity is by using character classes for each alphabetic, therefore your example would be more like [aA][bB][cC]. Individual character class matches are often implemented as bit-set lookups where a bit set containing 1s in the positions corresponding to a and A is built at regular expression -> DFA compile time.
That means that to match [aA] the DFA need only take the value of the input character, use it as an index to the bit-set - which is an O(1) operation - so you don't see the combinatoric time explosion that your equivalent
"abc|abC|aBc|aBC|Abc|AbC|ABc|ABC"
would suggest. DFA construction from regular expressions is an application of "if you are willing to spend some time up front (DFA building) you can really save cycles later (DFA recognition).
