Time Complexity

Question 1

Time Complexity in increasing order

Answer 1

O(1) < O(log n) < O(n) < O(n log n) < O(2^n) < O(n!)

Question 2

Time complexity of NP complete problems

Answer 2

Factorial or Exponential

Question 3

Exponential time vs Factorial time

Answer 3

Exponential time < Factorial time

Question 4

Examples of exponential time

Answer 4

2^n or x^n where x is any value. As n increases the time taken increases exponentially

Question 5

Examples of quadratic time

Answer 5

n^2, n^2 + x*n + c etc

Question 6

Quasilinear time

Answer 6

n * log n

Question 7

Polynomial time

Answer 7

n ^ c. eg. n^2, n^10 etc

Question 8

Log logarithmic time

Answer 8

log log n

Question 9

Which is greater 0.001 * 1.5^n or 1000 * n^3?

Answer 9

0.001 * 1.5^n&raquo_space;> 1000 * n^3. Exponential cannot be beaten by a polynomial

Question 10

What is amortized time?

Answer 10

Amortized time is the way to express the time complexity when an algorithm has the very bad time complexity only once in a while besides the time complexity that happens most of time.
Example ArrayList insert expands to double and saves for later operations.

Question 11

What is asymptotic analysis?

Answer 11

In Asymptotic Analysis, we evaluate the performance of an algorithm in terms of input size (we don’t measure the actual running time). We calculate, how does the time (or space) taken by an algorithm increases with the input size. Order of growth of algorithm with respect to input size

Question 12

In asymptotic analysis, 1000 * n log n vs 2 * n log n?

Answer 12

Both are same for asymptotic analysis which is O(n log n). We ignore constants.

Question 13

Let’s say Selection sort takes T(n) = n^2 to run. If sorting a deck of cards took 2 hours, how long will it take to sort 10 decks of unsorted cards?

Answer 13

First T(10*n) / T(n) = (10*n)^2 / n * 2 = 100.
100 times more time will be required, so 2 * 100 = 200 hours.

Question 14

Time complexity of Power Set?

Answer 14

Exponential. O(2^n). Consider example of fragrances that can be created with set of flowers. With every new flower, the number of fragrances doubles. So it is exponential.

Question 15

What is power set?

Answer 15

A power set is a set of all possible subsets of the set. So for a set A = {1, 2, 3}, the power set will be PowerSet(A) = {{}, {1}, {2}, {1,2}, {3}, {1, 3}, {2, 3}, {1, 2, 3}}

Question 16

What is rate of growth?

Answer 16

The rate at which the running time increases as a function of input is called rate of growth.

Question 17

Which are the three types of analysis of algorithms

Answer 17

1) Best case (Lower bound)
Defines the input for which the algorithm takes least time
2) Average case (Average time)
Provides prediction about running time of algorithm, Assumes input is random
3) Worst case (Upper bound)
Defines input for which algorithm takes long time

Question 18

Big Oh notation? Which type of bound is it?

Answer 18

Big O is asymptotic tight upper bound of the given function.
For example if f(n) = n^4 + 100n^2 + 10n + 20, then O(n^4) is the rate of growth as for higher values of n, as n^4 gives maximum rate of growth for f(n) at larger values of n.

Question 19

Omega notation? Which type of bound is it?

Answer 19

Omega is tighter lower bound and is represented as Omega(g(n)). It is asymptotic tight lower bound for f(n).

Question 20

Formal definition of Big O?

Answer 20

O(g(n)) = {f(n): there exists positive constants c and n0 such that 0 <= f(n) <= c*g(n) for all n >= n0}
Our objective is to give smallest rate of growth g(n) which is greater than or equal to given algorithms rate of growth f(n).

Question 21

Formal definition of Omega?

Answer 21

Omega(g(n)) = {f(n): There exists positive constants c and n0 such that 0 <= c*g(n) <= f(n) for all n >= n0}

Question 22

What is Theta notation?

Answer 22

This notation decides whether the upper and lower bound of a given function are same. The average running time of algorithm is always between lower bound and upper bound. If lower and upper bound give same result then theta will also have same rate of growth.
For example f(n) = 10*n + n
The tight upper bound g(n) is O(n). The rate of growth in best case Omega is Omega(n). In this case Theta will also be n.

Question 23

How do we calculate Theta when lower and upper bounds differ?

Answer 23

If rate of growths of lower and upper bound are not same then the rate of growth Theta case may not be same. In this case, we need to consider all possible time complexities and take average of those, in quick sort for example.

Question 24

Formal definition of Theta?

Answer 24

Theta(g(n)) = {f(n): there exist positive constants c1, c2, n0 such that 0<= c1g(n) <= f(n) <= c2g(n) for all n >= n0}

Question 25

Is there any importance of knowing Omega or best case time of algorithm?

Answer 25

No there is no practical importance of finding lower bound. So we find upper bound O and use Theta when lower and upper bound are same.

Question 26

Why is rate of growth called Asymptotic analysis?

Answer 26

We are trying to find function g(n) which approximates f(n) at higher values of n. That means g(n) is also a curve which approximates f(n) at higher values of n. In mathematics such a curve is called Asymptotic curve. That is why we call algorithm analysis asymptotic analysis.

Question 27

Explain logarithm complexity

Answer 27

In logarithm complexity if it takes constant time to cut the problem by fraction (1/2).
for (int i=1;i

Question 28

Explain logarithm complexity

Answer 28

In logarithm complexity if it takes constant time to cut the problem by fraction (1/2).
for (int i=1;i

Question 29

Common log formulas

Answer 29

log x*y = log x + log y
log x/y = log x - log y
log x^y = y log x
log^k n = (log k)^n
log base b (x) = log base a (x) / log base a (b)
a^log base b (x) = x^log base b (a)

Question 30

Arithmetic series

Answer 30

1 + 2 + ….. + n = n (n + 1) / 2

Question 31

Geometric series

Answer 31

1 + x^1 + x^2 + x^3 + …. + x^n = x^(n+1) - 1 / x - 1

Question 32

Harmonic series

Answer 32

1 + 1/2 + 1/4 + …. + 1/n = log n

Question 33

Master theorem for Divide and Conquer

Answer 33

2T(n/2) + O(n)

Question 34

Geometric series

Answer 34

1 + x^1 + x^2 + x^3 + …. + x^n = x^(n+1) - 1 / x - 1

Question 35

Harmonic series

Answer 35

1 + 1/2 + 1/4 + …. + 1/n = log n

Question 36

Master theorem for Divide and Conquer

Answer 36

2T(n/2) + O(n)

Question 37

Solve time complexity for T(n) = 3*T(n - 1)

Answer 37

T(n) = 3 * T(n - 1)
 = 3 * 3 * T (n - 2)
 = 3 ^ 3 * T (n - 3)
 = ....
 = 3 ^ n * T (n - n) = 3 ^ n * T(0) = 3 ^ n

So time complexity is 3 ^ n

Question 38

What is upper bound for n!?

Answer 38

n ^ n is upper bound for n!

Question 39

What is upper bound for log (n!)?

Answer 39

We know that upper bound for n! is n ^ n, so using that we have upper bound for log (n!) to be log (n ^ n) = n log n.
So answer is n log (n)