GER     A := A+α x (y^T)

Exit[]

n = 2500

timings

timL={{16.0,6.7034852328530294 10^-07},{32.0,1.3828721178694235 10^-06},{48.0,2.2301137953416459 10^-06},{64.0,3.1869931500735073 10^-06},{80.0,4.9420049731592215 10^-06},{96.0,7.7364456204310568 10^-06},{112.0,1.3690507358064384 10^-05},{128.0,1.7191625461984141 10^-05},{144.0,2.206732109518826 10^-05},{160.0,2.6506368159167509 10^-05},{176.0,3.2451346230176614 10^-05},{192.0,3.7775480189515155 10^-05},{208.0,4.4573360359646896 10^-05},{224.0,5.2875792185881669 10^-05},{240.0,6.2147218691754199 10^-05},{256.0,7.7865698503026687 10^-05},{272.0,9.2766577790984449 10^-05},{288.0,0.00011048169591397673},{304.0,0.00012706628923192311},{320.0,0.0001431047401861372},{336.0,0.00016134557321310474},{352.0,0.00017567168420356104},{368.0,0.00019353095758197617},{384.0,0.00021107007226811131},{400.0,0.00022859872756902369},{416.0,0.00025234426848295879},{432.0,0.00027636690120057093},{448.0,0.00031185354577621259},{464.0,0.00033865955121562409},{480.0,0.00035691038954176744},{496.0,0.00043108471536502707},{496.0,0.00042838494831481429},{528.0,0.0006263631654990227},{560.0,0.00099284089273119088},{592.0,0.001580111069797889},{624.0,0.002094476276408731},{656.0,0.0025119253384327496},{688.0,0.002827702701437191},{720.0,0.0031096347960099737},{752.0,0.0033925875045114},{784.0,0.0036825167250209181},{816.0,0.0039825587003479729},{848.0,0.004298080895257351},{880.0,0.004624821554686992},{912.0,0.0049747268979085484},{944.0,0.0053172137430394411},{976.0,0.0056786896447719917},{1008.0,0.0060589403867955397},{1040.0,0.0064795031612589404},{1072.0,0.0068530322336487889},{1104.0,0.0072625720686461592},{1136.0,0.0076896366180706109},{1168.0,0.0081274671949154043},{1200.0,0.008576793105219643},{1232.0,0.0090367347905736233},{1264.0,0.0095060450814187045},{1296.0,0.010001577651640491},{1328.0,0.01048268120391737},{1360.0,0.01100005989272124},{1392.0,0.011509332330867521},{1424.0,0.012051018259464993},{1456.0,0.01259609147467966},{1488.0,0.013152062941203817},{1520.0,0.01372432809742165},{1552.0,0.014304055890218787},{1584.0,0.014897482328150548},{1616.0,0.015506953338415624},{1648.0,0.016116187109157021},{1680.0,0.016753147580306858},{1712.0,0.017390652061513804},{1744.0,0.018049262320326085},{1776.0,0.018721931576916859},{1808.0,0.019387734338579488},{1840.0,0.020086634610370264},{1872.0,0.020780599606459966},{1904.0,0.021505360685474463},{1936.0,0.022222363515953421},{1968.0,0.022961973715302265},{2000.0,0.023713154290978877},{2032.0,0.024465376124366306},{2064.0,0.025244608461815865},{2096.0,0.026059210316437403},{2128.0,0.026863180591002341},{2160.0,0.027650890604470246},{2192.0,0.02845678994710471},{2224.0,0.029323964871231734},{2256.0,0.030179635189431907},{2288.0,0.03102288810173617},{2320.0,0.031905788306054117},{2352.0,0.032777637374118249},{2384.0,0.033698985822065979},{2416.0,0.034593812319163988},{2448.0,0.035534061674260792},{2480.0,0.036430480619871058}};

cost ?

n + 2 n^2    (or 3 n^2) ?

lp=ListPlot[timL]

par=Fit[timL,{1,x,x^2},x];

Show[lp,Plot[par,{x,0,2500}, PlotStyle->Red]]

Show[
Plot[par,{x,0,700}, PlotStyle->Red],
ListPlot[Select[timL,#[[1]]<700&]]
]

n < 510

threshold=510;

parS=
Fit[
Select[timL,0<#[[1]]<threshold&],
{1,x,x^2},x];

Show[
Plot[parS,{x,0,threshold}, PlotStyle->Red],
ListPlot[Select[timL,0<#[[1]]≤threshold&]]
]

Show[
Plot[parS,{x,0,2000}, PlotStyle->Red],
ListPlot[timL]
]

parL=
Fit[
Select[timL,threshold<#[[1]]&],
{1,x,x^2},x];

Show[
Plot[parL,{x,threshold,2500}, PlotStyle->Red],
ListPlot[Select[timL,threshold<#[[1]]&]]
]

Performance

perf[size_,time_]:=2 size^2/time

ListPlot[
Map[{#[[1]],perf[#[[1]],#[[2]]]}&,timL],
Joined->True
]

ListPlot[
Map[
{#[[1]],perf[#[[1]],#[[2]]]}&,
Select[timL,#[[1]]<700&]
],
Joined->True
]

Size

size[n_]:=(n^2+2n) 8./1024

size[90]

Solve[size[x]==64,x]

Solve[size[x]==512,x]

Solve[size[x]==2048,x]

par90=
Fit[
Select[timL,0<#[[1]]≤90&],
{1,x,x^2},x];

Show[
Plot[par90,{x,0,90}, PlotStyle->Red],
ListPlot[Select[timL,0<#[[1]]≤90&]]
]

par255=
Fit[
Select[timL,90<#[[1]]≤255&],
{1,x,x^2},x];

Show[
Plot[par255,{x,90,255}, PlotStyle->Red],
ListPlot[Select[timL,90<#[[1]]≤255&]]
]

par511=
Fit[
Select[timL,255<#[[1]]≤511&],
{1,x,x^2},x];

Show[
Plot[par511,{x,255,511}, PlotStyle->Red],
ListPlot[Select[timL,255<#[[1]]≤511&]]
]

parUP=
Fit[
Select[timL,511<#[[1]]&],
{1,x,x^2},x];

Show[
Plot[parUP,{x,511,2500}, PlotStyle->Red],
ListPlot[Select[timL,511<#[[1]]&]]
]

Show[{
ListPlot[Select[timL,#[[1]]≤2000&]],
Plot[par90,{x,0,90}, PlotStyle->Red],
Plot[par255,{x,90,255}, PlotStyle->Green],
Plot[par511,{x,255,511}, PlotStyle->Brown],
Plot[parUP,{x,511,2500}, PlotStyle->Red]
}
]