Question

Recall that to multiply an m×n matrix by an n×k matrix requires m×n×k multiplications. The Google PageRank algorithm uses a square matrix that’s filled with non-zero entries when pages link to one another. Suppose we have m web sites cataloged: this is then an m×m matrix. Denote this matrix by P. P is then run through an iterative algorithm that takes j loops to complete (for 5 < j < 100), and each step of this loop an m×m matrix is multiplied by P.

a. mj log m
b. m^2
c. m^3
d. m^4
e. m^2j^2
f. m^2log m

Answer 1

Answer:

option C i.e. m^3 is the correct option.

Explanation:

The Multiplication of one m x m matrix with a different m x m matrix will take time m x m x m = m3

And given that this multiplication occurred for j iterations, therefore, the total number of multiplication will be j * m3 = jm3

Consequently, the complexity order will be jm3

Since 5< j < 100, hence j can be substituted by constant and for this reason among all the options mentioned, option C i.e. m^3 is correct.