The Student Room Group

Time complexity

I'm still very confused as to where everything originates from.
I'm looking at a basic example of a matrix A multiplied by a vector x which equals b, ie, Ax = b.

A is an nxn matrix, and x and b are nx1 vectors.

My notes say there are n^2 scalar multiplications and n(n-1) scalar additions and for the life of me I can't understand how these are constructed.

The top line of the calculation of b1 would be:

a_1_1*x_1 + a_1_2*x_2 + ... + a_1_1-n*x_n-1 + a_1_n*x_n = b_1

So we have n additions to create b_1 and n multiplications to create b_1, but I don't know how this relates to the rest of each to get n^2 and n(n-1)...

We have n-1 more of these additions and multiplications for the rest of b_2 up to b_n? I don't know, please help!
Original post by Bameron
I'm still very confused as to where everything originates from.
I'm looking at a basic example of a matrix A multiplied by a vector x which equals b, ie, Ax = b.

A is an nxn matrix, and x and b are nx1 vectors.

My notes say there are n^2 scalar multiplications and n(n-1) scalar additions and for the life of me I can't understand how these are constructed.

The top line of the calculation of b1 would be:

a_1_1*x_1 + a_1_2*x_2 + ... + a_1_1-n*x_n-1 + a_1_n*x_n = b_1

So we have n additions to create b_1 and n multiplications to create b_1, but I don't know how this relates to the rest of each to get n^2 and n(n-1)...

We have n-1 more of these additions and multiplications for the rest of b_2 up to b_n? I don't know, please help!


Suppose you had a 2x2 matrix for simplicity. How many additions and multiplications do you have? Then try a 3x3 matrix.
Original post by Bameron
I'm still very confused as to where everything originates from.
I'm looking at a basic example of a matrix A multiplied by a vector x which equals b, ie, Ax = b.

A is an nxn matrix, and x and b are nx1 vectors.

My notes say there are n^2 scalar multiplications and n(n-1) scalar additions and for the life of me I can't understand how these are constructed.

The top line of the calculation of b1 would be:

a_1_1*x_1 + a_1_2*x_2 + ... + a_1_1-n*x_n-1 + a_1_n*x_n = b_1

So we have n additions to create b_1 and n multiplications to create b_1, but I don't know how this relates to the rest of each to get n^2 and n(n-1)...

We have n-1 more of these additions and multiplications for the rest of b_2 up to b_n? I don't know, please help!


You have n-1 additions and n multiplications to create b_1.

Same is true for b_2, b_3, etc. You have to do this for each of the n values, b_1 to b_n.

Hence n times.

So, n(n-1) additions and n x n multiplcations.

Quick Reply

Latest