# Why would A \\ b grow with O(n^2)?
**URL:** https://discourse.julialang.org/t/why-would-a-b-grow-with-o-n-2/106083
**Category:** Numerics
**Tags:** question, linearalgebra
**Created:** [November 11, 2023, 4:46pm UTC](https://discourse.julialang.org/t/why-would-a-b-grow-with-o-n-2/106083 "2023-11-11T16:46:20Z")
**Posts on this page:** 6
**Page:** 1
### Author:  [@tawheeler](https://discourse.julialang.org/u/tawheeler)
#### Post date: [November 11, 2023, 4:46pm UTC](https://discourse.julialang.org/t/why-would-a-b-grow-with-o-n-2/106083/1 "2023-11-11T16:46:20Z")
Hello,
I was curious how long it would take my laptop to solve Ax = b for square A as a function of the problem size. I tried to profile it using BenchmarkTools:
```julia
ns = [1,2,3,5,7,10,20,30,50,70,100,200,300,500,700,1000,2000,3000,5000,7000,10000]
ts = Array{Float64}(undef, length(ns))
for (i,n) in enumerate(ns)
b = @benchmark $(rand(n,n)) \ $(rand(n))
ts[i] = median(b).time
end
```
and found that it seems to grow quadratically, in O(n^2). I expected it to grow in O(n^3).
The gray trendline is n^2 / 10^7.
I’m running Julia single-threaded and the matrices are dense, so I am not sure why this would be. Is there something wrong with how I am benchmarking it? Is there some property of positive dense matrices that I am missing? Is it actually using multiple threads under the hood?
Thank you!
---
### Author:  [@nilshg](https://discourse.julialang.org/u/nilshg)
#### Post date: [November 11, 2023, 5:39pm UTC](https://discourse.julialang.org/t/why-would-a-b-grow-with-o-n-2/106083/2 "2023-11-11T17:39:52Z")
> [@tawheeler](#):
>
> Is it actually using multiple threads under the hood?
I think this is just using BLAS so unless you set BLAS threads to 1 it’s probably multi threaded.
---
### Author:  [@tawheeler](https://discourse.julialang.org/u/tawheeler)
#### Post date: [November 11, 2023, 5:55pm UTC](https://discourse.julialang.org/t/why-would-a-b-grow-with-o-n-2/106083/3 "2023-11-11T17:55:16Z")
I think you are right. `LinearAlgebra.BLAS.get_num_threads()` is telling me BLAS can use up to 8 threads.
I figured out how to set the number of BLAS threads. Will verify that. Thank you!
---
### Author:  [@Elrod](https://discourse.julialang.org/u/Elrod)
#### Post date: [November 11, 2023, 6:10pm UTC](https://discourse.julialang.org/t/why-would-a-b-grow-with-o-n-2/106083/4 "2023-11-11T18:10:25Z")
The cost is probably dominated by `lu`, which in practice scales much better than O(N^3) up to extremely large sizes.
---
### Author:  [@tawheeler](https://discourse.julialang.org/u/tawheeler)
#### Post date: [November 11, 2023, 8:56pm UTC](https://discourse.julialang.org/t/why-would-a-b-grow-with-o-n-2/106083/5 "2023-11-11T20:56:04Z")
Setting BLAS to use 1 thread is giving me O(n^3) scaling starting around n=200. Thank you!
---
### Author:  [@dlfivefifty](https://discourse.julialang.org/u/dlfivefifty)
#### Post date: [November 12, 2023, 8:03am UTC](https://discourse.julialang.org/t/why-would-a-b-grow-with-o-n-2/106083/6 "2023-11-12T08:03:00Z")
Relevant article by Nick Trefethen: [https://people.maths.ox.ac.uk/trefethen/sept23lms.pdf](https://people.maths.ox.ac.uk/trefethen/sept23lms.pdf)