Let $b$ be the bit width of the input and output of $E^{(1)}$ and $E^{(2)}$. For DES that would be $b=64$, with $n=56$. Assume $b\ge k+4$, which holds for DES, and simplifies some approximations.

I'm assuming the function iterated has $b$-bit result, so that any collision found with a usable discriminator bit ensures that $c=E^{(2)}_{K_2}(E^{(1)}_{K_1}(p))$ where $K_1$ and $K_2$ are derived from the colliding inputs, and the common output is $E^{(1)}_{K_1}(p)$. This particular $K_1$ pair $K_2$ has odds about $2^{b-2n}=2^{-48}$ to be correct (and that's checked with negligible cost, just as in the normal MitM).

I see no reason why the proposed method would not find collision with a usable discriminator bit as expected for a random function, at an expected cost of about $2^{b/2+1}$ evaluations of the function (only a little more with cycle-finding using distinguished points). So the expected cost is like $2^{2n-b/2+1}=2^{81}$.

Using little RAM comes at the price of making about $2^{n-b/2+1}=2^{25}$ more evaluations of $E^{(1)}$ and $E^{(2)}$ (I have silently dropped small factors here and there, but hope this holds within a factor of 2). It's hard to tell if, and when, this might be preferable in practice to the most obvious time-memory tradeoff to MitM, where we split the problem into $2^r$ runs each using a more manageable table of $2^{n-r}$ entries, for an expected $2^{r+n+1}$ evaluations of an $E^{(1)}$ or $E^{(2)}$ (for parallel runs).

A compromise may be possible; this is studied in the [section on MitM][1] in Paul C. van Oorschot and Michael J. Wiener: _Parallel Collision Search with Cryptanalytic Applications_ (in [Journal of Cryptology, January 1999, Volume 12, Issue 1][2]), which I think supersedes their earlier [_Improving Implementable Meet-in-the-Middle Attacks by Orders of Magnitude_][3] (in proceedings of Crypto 1996).


  [1]: http://people.scs.carleton.ca/~paulv/papers/JoC97.pdf#page=16
  [2]: http://link.springer.com/article/10.1007/PL00003816
  [3]: http://link.springer.com/chapter/10.1007/3-540-68697-5_18