I dont think grep -i is exponentially (wrt 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?