Time Complexity

(Skip to the end of this document for time complexity questions)

The intuition behind time complexity

Time complexity is not really about how long it would take for a program to execute. Rather, it is about how the execution time scales with the input size. At least, that is a reasonable approximation for programming interviews :)

Why is time complexity important in job interviews?

Many internet companies deal with large quantities of data, of the order of tera bytes or peta bytes. When dealing with such massive quantities of data, the difference between a less efficient algorithm (say O(n²)) algorithm and a more efficient one (say O(n)) can be significant.

Time complexity is probably important in programming interviews because they can be used as benchmarks to evaluate interviewees. The more efficient a solution, the less obvious it usually is. Hence they are often used to judge the problem solving skills of the interviewee.

Guess the time complexity for the following code snippets?

Basic questions

Question 1:

Question 2:

Challenging questions

Question 3

Question 4

Question 5

Answers

1. O(n²)
2. O(log n)
3. O(n)
4. O(n)
5. O(n²)

Additional Reading

By Programming Interview Prep