Expectation of Computational Complexity for a dense matrix linear system

Given a linear system: $A in mathcal{R}^{n times n}$

$$
A = begin{bmatrix}
n & 1 & 1 & cdots & 1 \
1 & n & 1 & cdots & 1 \
1 & 1 & n & cdots & 1 \
cdots & & & dots & n \
end{bmatrix}
$$
which has elements $n’s$ on the diagonal and $1’s$ everywhere, and $b = [1,2,…,n]^{T}$. Consider this linear system:

$$
Ax = b
$$

I am trying to find the expectation of execution time for this linear system with LU algorithm solving linear system and Gauss-Seidel method. For LU algorithm, I figured out using computational cost for LU is $W = frac{2}{3} n^{3} + 2n^{2} + O(n)$ deducing the ratio is near to $8$ when $n$ size is scaled by double its size. I tried to run the Gauss Seidel in python for problem sizes $n =250,500,1000,2000,4000$ the number of convergence iterations are $18,18,19,20,20$ respectively. However, for the method Gauss-Seidel, how can I find the execution time as a scale asymptotically as a function of $n$ ? I was given a hint that for number of iterations as a function of $n$ it is very specific for this type of matrix $A$.