General Time Complexity

Question 1

What is “Big O” notation?

Answer 1

f(n) is O(g(n)) as n → ∞

An upper-bound approximation of the behavior of f(n) as n approaches infinity

Question 2

What are the 6 main types of Big O?

Answer 2

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

Question 3

What are the 4 rules of Big O?

Answer 3

1. Assume worst case scenario
2. Remove constants
3. Remove non-dominants
4. Different inputs require different identifiers

Question 4

What is the time complexity for:

obj.method(n, o) {
n.forEach(...);
o.forEach(...);
}

Answer 4

O(n + o)

Question 5

What is the time complexity for:

obj.method(n) {
n.forEach(e -> n.forEach(...));

Answer 5

O(n^2)

Question 6

What is the time complexity for:

obj.method(n) {
n.forEach(...);
n.forEach(e -> n.forEach(...));
}

Answer 6

O(n^2)

Question 7

What is the time complexity for:

obj.method(n, o) {
n.forEach(e -> o.forEach(...));
}

Answer 7

O(n * o)

Question 8

What does “amortized constant time” mean?

Answer 8

It means O(1) most of the time, but O(n) in rare occasions. An example would be dynamic arrays that have readhed their capacity

Question 9

1. What is the time complexity of a binary search algorithm?
2. What are the 2 requirements for using a binary search algorithm?

Answer 9

1. O(log(n))
2. 1. Sorted data
      Or
   2. A binary decision to reduce search range by half

Question 10

What are the different ways to think about O(log n)?

Answer 10

1. As n doubles, the number of operations increases by 1
2. The number of operations can be determined by continuously dividing n by 2 until it produces a value <= 1

Question 11

Logarithms are the inverse of…

Answer 11

Exponents

For example:
2^3 = 2 * 2 * 2
is the inverse of
log(8) = 8/2 4/2 2/2

Question 12

Could 2 different algorithms with the same Big O have different speeds?

Answer 12

Yes

Question 13

Describe how to analyze the time complexity of a recursive algorithm

Answer 13

For each recursive invocation, account for the number of operations performed within its body. Multiply that sum by the number fo recursive invocations performed. (This is also how a person would analyze the time complexity of an algorithm that calls another method)

Question 14

What is the purpose of Big O?

Answer 14

The purpose of Big O is to classify the computational complexity of an algorithm

Question 15

What is time complexity?

Answer 15

Time complexity is the amount of time an algorithm needs to compute relative to the input size

Question 16

What is space complexity?

Answer 16

Space complexity is the amount of memory an algorithm needs to compute relative to the input size

Question 17

When dealing with computational complexity, what are the 3 general types of cases?

Answer 17

1. Best case
2. Average case
3. Worst case

Question 18

What is the time complexity for most efficient sorting algorithms?

Answer 18

O(n * log(n))

Question 19

True or False

We never count the space used by the input (it is bad practice to modify the input), and usually don’t count the space used by the output (the answer) unless an interviewer asks us to

Answer 19

True