It would average the same size as the actual data. Treating the pi bit sequence as random bits, and ignoring overlap effects, the probability that a given n bit sequence is the one you want is 1/2^n, so you need to try on average 2^n sequences to find the one you want, so the index to find it is typically of length n, up to some second order effects having to do with expectation of a log not being the log of an expectation.