Let’s assume we have a computer that can solve a 100 times 100 system in 1 second using Gauss elimination. Estimate the time required to solve the following problems on the same computer. You must indicate the scaling as well as the time. (a) 1000 times 1000 system using Gauss elimination (b) 1000 times 1000 system with a band structure p = q = 2 using banded Gauss elimination (c) The original 100 times 100 system using an iterative method with 10 iterations.

## Expert Answer

The complexity of gauss elimination is O(n^{3})

a) If 100X100 system can be solved in 1 second i.e

than

1000X1000 system can be solved 10^{3} * 1 second

b)Even with band structure the complexity is in order of n^{3}

so time required to solve the problem is 10^{3} seconds

(c) The iterative method decrease the time on the cost of error.

In 10 iterations it required 1/10^{3} second only