It's efficient enough, given its a 2D plattform jump&run game. The developer wrote an extensive article how it works, it's really interesting, search for it.

Game creator Jonathan Blow explains the rewind in a video (27min): http://www.youtube.com/watch?v=tSeYShR-OG0

And there is Gamasutra article about Rewind, in four parts: http://gamasutra.com/blogs/CameronLeBlanc/20130220/187036/Re... and part 2-3: http://www.gamasutra.com/blogs/CameronLeBlanc/20130313/18844...