Data Structures & Algorithms

Question 1

What is Big O Notation?

Answer 1

A numeric representation of the efficiency of code

Question 2

Big O Notation is a ____ way of talking about how efficient an algorithm is.

Answer 2

Generalized.

Question 3

0(n)

Answer 3

Linear time complexity. The algorithm’s runtime increases linearly with the input size.

Question 4

0(1)

Answer 4

Constant time complexity. The algorithm’s runtime is constant regardless of the input size.

Question 5

0(n^2)

Answer 5

Quadratic time complexity. The algorithm’s runtime increases quadratically with the input size.

Question 6

Time complexity describes…

Answer 6

how an algorithm’s performance scales as the size of the input increases.

Question 7

Auxiliary space complexity…

Answer 7

refers to the amount of additional memory space required by an algorithm beyond the input size to solve a problem.

Question 8

Rules of Thumb for space complexity:
1) Most primitives (booleans, numbers, undefined, null)….
2) Strings require ____ space …
3) Reference types are generally ____ space…

Answer 8

1) Take up constant space.
2) O(n) space … where n is the string length.
3) O(n) space … where n is the length (for array’s) or the number of keys (objects).

Question 9

O(logN)

Answer 9

O(logN) time complexity, refers to a situation where the number of steps necessary to complete a task increases in proportion to the logarithm of the input size.

Question 10

O(NLogN)

Answer 10

time complexity represents a scenario where the time an algorithm takes grows in proportion to N (the size of the input) multiplied by logN (the logarithm of N).
This complexity is seen in algorithms that perform a logarithmic operation multiple times, once for each element in the input.

Question 11

O(2^N)

Answer 11

Represents exponential time complexity. Signifies that the execution time of an algorithm grows exponentially with the size of the input. For each additional element in the input, the execution time of the algorithm doubles.

Question 12

What is a good example of an algorithm with exponential time complexity?

Answer 12

A common example of an algorithm with exponential time complexity is non-memoized recursion. In such cases, the algorithm often recalculates the same subproblems multiple times, leading to a dramatic increase in the number of operations.