Data structures and Algorithms

Question 1

What is time complexity analyzed for?

Answer 1

1) Very large input size

2) Worst case scenario

Question 2

What is the time complexity of T(n) = 2n^2+3n+1?

Answer 2

1) Drop lower order terms
2) Drop constants

Time complexity is O(N) = n^2

Question 3

How do you calculate the time complexity of a single loop?
for (int i = 1; i <= n; i++)
{
 x = y + z;
}

Answer 3

for (int i = 1; i <= n; i++)
{
 x = y + z; //constant time - C
}
Time complexity is C*N. Since you traverse N number of elements.

Question 4

How do you calculate the time complexity of a nested loop?

Answer 4

1) Figure out how many times each loop will pass

2) Multiply each loop

Question 5

How do you calculate time complexity of sequential statements?

Answer 5

You add the time complexities of each statement.

Question 6

How do you calculate time complexity of if else statements?

Answer 6

You take the worse complexity of the two conditions.

Question 7

What is the order of time complexities

O(logN), O(NlogN), O(n!), O(1), O(n), O(c^n), O(n^c). From worst to best.

Answer 7

O(n!) > O(c^n) > O(n^c) > O(NLogN) > O(n) > O(logN) > O(1)

Question 8

What is the time complexity of selection sort?

Answer 8

Best: n^2
Average: n^2
Worst: n^2

Question 9

What is the time complexity of bubble sort?

Answer 9

Best: `n
Avergage: n^2
Worst: n^2

Question 10

What is the time complexity of insertion sort?

Answer 10

Best: n
Average: n^2
Worst: n^2

Question 11

What is the time complexity of heap sort?

Answer 11

All: NLogN

Question 12

What is the time complexity of quick sort?

Answer 12

Best, Average: NlogN

Worst: N^2

Question 13

What is the time complexities of merge sort?

Answer 13

All: NlogN

Question 14

What is the time complexities of bucket sort?

Answer 14

Best, Average: N+K

Worst: N^2

Question 15

What is the time complexities of radix sort?

Answer 15

Best, Average, Worst: N*K

Question 16

What is the space time trade-off?

Answer 16

The more time efficiency you have, the less space efficiency you have and vice versa.