Rebranding is not too difficult if you don't get much traffic from organic search. It's a simple redirect and a notice on the page.

It's also not too difficult when you're small but gets more costly as time goes on. If DDG succeeds, the customer base it has now will be something like .00001% of it's users.