The good thing is that most operations on most data-structures (as well as many of the more common algorithms) don't require solving recurrence equations to determine their asymptotic growth, usually our intuition based on counting tends to be pretty close.
Sketch out your basic data structures on a piece of paper, then just use your finger to trace out how you could do insert, delete, search, etc you can usually tell if something is taking O(lg n), O(n), O(n lg n), etc just by counting the steps you take. After you're comfortable with this, sketch it in your head. You can't forget something that you understand.
The point is that if figuring what out Big O is seems like something you have to memorize to recall quickly, then you very likely don't really understand the underlying data structure/algorithm (and as such you rightfully should do poorly on algorithms interviews). Take the time to make sure you really understand what's going on, and everything else should fall into place.
Sketch out your basic data structures on a piece of paper, then just use your finger to trace out how you could do insert, delete, search, etc you can usually tell if something is taking O(lg n), O(n), O(n lg n), etc just by counting the steps you take. After you're comfortable with this, sketch it in your head. You can't forget something that you understand.
The point is that if figuring what out Big O is seems like something you have to memorize to recall quickly, then you very likely don't really understand the underlying data structure/algorithm (and as such you rightfully should do poorly on algorithms interviews). Take the time to make sure you really understand what's going on, and everything else should fall into place.