How do you state the complexity of a solution clearly during an interview?
You say the complexity in the same three sentences every time, and you say it before you say anything else about the solution.
def analyse(data):
operations = 0
for value in data:
operations += 1
return operations
So what are the three sentences? Here they are.
the sentence what it says
------------------------------ --------------------------------------------
"the time is O of ..." the big O in terms of the input size
"the space is O of ..." the extra memory you use
"because ..." why, in one short reason
And the third sentence is the one that makes the difference. Saying "the time is O of n" is a claim. Saying "the time is O of n because each item is looked at once and each step is a constant amount of work" is an explanation, and the interviewer knows that you understand rather than guessed.
the weak answer the strong answer
---------------------------- -----------------------------------------------
"it is O of n" "it is O of n because we go through the
list once and each step is constant"
"the space is O of 1" "the space is O of 1 because we only keep
a running total and the input list"
And there is one more sentence that is worth adding at the end, and it is the one that tells the interviewer you are thinking about the real world. You can say how the time changes when the input grows ten times bigger. So "the time is O of n, so a list ten times bigger takes ten times as long" is a good closing line.
And there is a way to check your own claim, and it is worth knowing about. Count the operations with a counter and run it on a few sizes, and then look at how the count grows.
the input size the operations
---------------- -------------
10 10
100 100
1000 1000
the count goes up ten times each time, so it is O of n
And there is one detail that catches people out under pressure. You have to say the space for the extra memory and not for the input. If you sort the list in place then the space is O of 1, and if you make a copy then it is O of n. The interviewer is interested in what your code adds, because that is what your program has to hold in memory.
So the rule to remember is this. Say the big O, say the space, and then give the reason.
The next two questions in this topic show the operation counts and what to do when you are wrong.