Input Constraints

Question 1

What time complexity/approach should you be thinking of for an input size of N = < 10 ?

Answer 1

Some logrithmic approach with higher than base 2; think backtracking/brute-force. Any algorithm that finds the correct answer is fine, this is non-restrictive.

Question 2

What time complexity/approach should you be thinking of for an input size of 10 < N = < 20 ?

Answer 2

This is a non-restrictive condition, look for backtracking/recursion. Likely you are considering all possible subsets.

Question 3

What time complexity/approach should you be thinking of for an input size of 20 < N = < 100 ?

Answer 3

Exponentials are too slow, cubic maybe.

Look for a brute force nested loop. Start with brute force and look for enhancements with hash maps or heaps.

Question 4

What time complexity/approach should you be thinking of for an input size of 100 < N = < 1000 ?

Answer 4

Look for a nested loop solution, likely this is the optimal route.

Question 5

What time complexity/approach should you be thinking of for an input size of 1,000 < N = < 100,000 ?

Answer 5

This is the most common constraint

Acceptable: O(n * log(n))
Goal: O(n)

Think about sorting or a heap. Any classic algorithm will be needed, sliding window, binary search, etc. Large constants are ok, eg looping over the Alphabet is O(26n)

Question 6

What time complexity/approach should you be thinking of for an input size of 100,000 < N = < 1,000,000 ?

Answer 6

Will likely need O(n), maybe O(nlog(n)). Think of a hashmap.

Question 7

What time complexity/approach should you be thinking of for an input size of 1,000,000 < N ?

Answer 7

Will need to be O(log(n)) or O(1). Use clever math or binary search or hashmaps.

Question 8

What is the time complexity for the build in sorting method in Python?

Answer 8

O(nlog(n)), using Timsort