Answers to Hacks Questions

  1. Time and space complexity are important when choosing an algorithm because they determine how much time and memory is required to solve a problem. An efficient algorithm requires less time and memory.

  2. I should not always use a constant time algorithm, and I should never use an exponential time algorithm. The choice of an algorithm depends on a specific problem you are trying to solve and the trade-offs between time and space complexity. In some cases, a constant time algorithm may not be able to solve the problem efficiently, while in other cases, an exponential time algorithm may be the only practical solution. It is important to consider the constraints and requirements of the problem at hand when choosing an algorithm.

  3. Some general patterns that I noticed to determine each algorithm’s time and space complexity are recursive functions, analyzing loops, and nested data structures. To determine time complexity you need to count the number of operations executed by an algorithm related to/caused by the input size. To determine space complexity, you to analyze the amount of memory required to store data as a function of the input size.

Time Complexity Analysis Questions

Question 1

What is the time and space complexity of the following code?

a = 0
b = 0
for i in range(N):
  a = a + random()
 
for i in range(M):
  b = b + random()
  1. O(N * M) time, O(1) space
  2. O(N + M) time, O(N + M) space
  3. O(N + M) time, O(1) space
  4. O(N * M) time, O(N + M) space

My answer: 3

Question 2

What is the time complexity of the following code?

a = 0
for i in range(N):
  for j in reversed(range(i,N)):
    a = a + i + j
  1. O(N)
  2. O(N*log(N))
  3. O(N * Sqrt(N))
  4. O(N*N)

My answer: 4

Question 3 What is the time complexity of the following code?

k = 0
for i in range(n//2, n):
  for j in range(2, n, pow(2,j)):
        k = k + n / 2
  1. O(n)
  2. O(nlog(n))
  3. O(n^2)
  4. O(n^2(log(n)))

My answer: 2

Question 4 What does it mean when we say that an algorithm X is asymptotically more efficient than Y?

  1. X will always be a better choice for small inputs
  2. X will always be a better choice for large inputs
  3. Y will always be a better choice for small inputs
  4. X will always be a better choice for all inputs

My answer: 2

Question 5 What is the time complexity of the following code?

a = 0
i = N
while (i > 0):
  a += i
  i //= 2
  1. O(N)
  2. O(Sqrt(N))
  3. O(N / 2)
  4. O(log N) My answer: 4

Question 6 Which of the following best describes the useful criterion for comparing the efficiency of algorithms?

  1. Time
  2. Memory
  3. Both of the above
  4. None of the above

My answer: 3

Question 7 How is time complexity measured?

  1. By counting the number of algorithms in an algorithm.
  2. By counting the number of primitive operations performed by the algorithm on a given input size.
  3. By counting the size of data input to the algorithm.
  4. None of the above

My answer: 2

Question 8 What will be the time complexity of the following code?

for i in range(n):
  i=i*k
  1. O(n)
  2. O(k)
  3. O(logk(n))
  4. O(logn(k))

My answer: 3

Question 9 What will be the time complexity of the following code?

value = 0 for i in range(n): for j in range(i): value=value+1

  1. O(n)
  2. O(n+1)
  3. O(n(n-1))
  4. O(n(n+1))

My answer: 3

Question 10 Algorithm A and B have a worst-case running time of O(n) and O(logn), respectively. Therefore, algorithm B always runs faster than algorithm A.

  1. True
  2. False

My answer: 2

Reflection on the practice problems: The practice problems helped me understand space and time complexity even better.