I have a function I'm trying to do a flop count on , but I keep getting 2n instead of n^2. I know its supposed to be n^2 based on the fact it's still a nxn triangular system that is just being solved in column first order. I'm new to linear algebra so please forgive me. I'll include the function , as well as all my work shown the best I can. Column BS Function

function col_bs(U, b)

    n = length(b)
    x = copy(b)

    for j = n:-1:2
        if U[j,j] == 0
            error("Error: Matrix U is singular.")
        end
        x[j] = x[j]/U[j,j] 

        for i=1:j-1
            x[i] = x[i] - x[j] * U[i , j ]
        end
    end

    x[1] = x[1]/U[1,1]


    return x
end

1. To start 2 flops for the addition and multiplication 𝑥[𝑖]−𝑥[𝑗]∗𝑈[𝑖,𝑗]

The 𝑖 loop does: ∑𝑖=𝑗−112

2. 1 flop for the division 𝑥[𝑗]/=𝑈[𝑗,𝑗]

3. Inside the for 𝑗 loop in total does: 1+∑𝑖=𝑗−112

4. The 𝑗 loop itself does: ∑𝑗=2𝑛(1+∑𝑖=𝑗−112))

5. Then one final flop for 𝑥[1]=𝑥[1]/𝑈[1,1].

6. Finally we have 1+(∑𝑗=2𝑛(1+∑𝑖=𝑗−112))).

Which we can now break down.

If we distribute and simplify 1+(∑𝑗=2𝑛+∑𝑗=2𝑛∑𝑖=𝑗−112).

We can look at only the significant variables and ignore constants,

1+(𝑛+𝑛(1))(𝑛+𝑛(1))𝑛+𝑛2𝑛

Which then means that if we ignore constants the highest possibility of flops for this formula would be 𝑛 ( which may be a hint to whats wrong with my function since it should be 𝑛2 just like the rest of our triangular systems I believe) Proof

Proof