Compute the big-O number of basic arithmetic operations required to do the follo

Question

Compute the big-O number of basic arithmetic operations required to do the following operations. (a) Compute the dot product of two vectors in R^n. (b) Compute the outer product of A = uv^T for u elementof R^n times 1. (c) Compute Ax for A elementof R^m times n and x elementof R^n. (d) Compute Ax, A elementof R^m times n and x elementof R^n when you have a (reduced) QR decomposition A = QR, Q elementof R^m times k, R elementof R^k times k. (e) Compute Ax for A = uv^T, u elementof R^m times, v elementof R^n times 1, and x elementof R^n. (f) Solve the least squares problem min_x ||Ax - b||^2. (g) Solve the least squares problem min_x ||Ax - b||^2 when you have a QR decomposition. A = QR, Q elementof R^m times k, R elementof R^k times k.

Explanation / Answer

Answer:1

1) Computaion of dot product of two vectors is as follows:

Lets assume we have vector x = [x1, x2, ....xn] and vector y = [y1, y2, ....yn] then there dot product will be:

x.y = x1.y1 + x2.y2 + .... xn.yn

so according to it the big O will be O(n) + O(n) = O(n)

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.