Skiena's algorithm book goes into some detail on proving complexity and proving optimality.

I personally like to go line by line in my solution and state the runtime of each line of code. Then I add them together, and write out the limit notation showing as N->inf and how I can cancel certain variables out. Its a little bit of overkill but I've found it helps me stand out a bit during interviews.

Usually on interviews it is not actual proving in any mathematical sort of way. It's more like: "I am calling sort() in a loop so obviously this is O(n^2 * log n) complexity" and then the interviewer nods in approval and you move on to the next question.