AtCoder: C - Go Home、時間計算量がなぜ√Xになるのか

Question

お伺いしたいこと

この問題
を等差数列を用いて回答した場合（　t(t+1)2 ≥ Xを判定し、これを満たすtを探す場合　）の計算量の求め方がわからないです。

詳細

解説に
t を前から順番に試して t(t+1)2 ≥ X か毎回判定するだけでも, 時間計算量 O(√X)で答えを求めることが出来ます。 とありますが、この時の計算量がなぜO(√X)となるのかがわかりませんでした。
助言頂けると幸いです

Answer 1

t(t+1)/2をt^2とします。(計算量を出すため、簡単にしておきます)
そうすると不等式はt^2>=Xとなります。
これを解くと, t>=√Xとなります。
つまり、tを小さいほうから代入してこの不等式をためすと, tが√Xくらいになると答えがわかることから、必要な計算量としてはO(√X)となります。

たとえばX=5とすると, t>=√5となりますが、tを順番に代入して試していくと,
t=1 t^2=1<X
t=2 t^2=4<X
t=3 t^2=9>X
となって、t=3が答えとわかります。だいたい√X=√5(=2.236)くらいのtの値まで調べれば十分なので時間計算量としてはO(√X)となります。

t*(t+1)/2のまま同じ議論をしてもオーダー的には√Xになるため、結局同じ結果になります。