Recall that to multiply an mn matrix by an nk matrix requires mnk multiplications. The Google PageRank algorithm uses a square matrix that's ﬁlled with non-zero entries when pages link to one another. Suppose we have m web sites cataloged: this is then an mm 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 mm 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

Question

Computers and Technology

Randall Ashley

9 September, 11:31

Recall that to multiply an mn matrix by an nk matrix requires mnk multiplications. The Google PageRank algorithm uses a square matrix that's ﬁlled with non-zero entries when pages link to one another. Suppose we have m web sites cataloged: this is then an mm 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 mm 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

+5

Answers (1)

Know the Answer?

Aidan Schmitt · Answer 1

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.