2
$\begingroup$

I am a little puzzled by the following test:

n = 60000;
expr = Nest[f, a, n];
pattern[k_] := Nest[f, a, k];

Timing[FreeQ[expr, pattern[#]]] & /@ {100, 200, 400, 800, 1600,
                                      3200, 6400, 12800, 25600}

which returns (with Mathematica 10):

{{0.008822, False}, {0.004429, False}, {0.005732, False}, {0.014171, 
  False}, {0.047446, False}, {0.186261, False}, {0.748414, 
  False}, {3.407582, False}, {15.070649, False}}

It occurs to me that the naive algorithm for testing the absence (or presence) of the deeply nested pattern[k] should have O(k n) complexity. (Even more, in Boyer-Moore algorithm for string pattern matching, the complexity diminishes when the pattern is big).

$\endgroup$
  • $\begingroup$ Look at the LevelSpec and its defaults... $\endgroup$ – ciao Jun 11 '15 at 6:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.