アルゴリズムの計算量を最悪評価するか平均評価するかとか細かい話があります。恥ずかしながら割と遅くまでクイックソートの最悪計算量が n^2 ということをちゃんとは把握していませんでした。乱択アルゴリズムは基本的にランダムネスを入れることで最悪の場合をできるだけ回避して平均計算量を減らせるという話だと思います。
その計算量の理論解析にはεネットの話とか学習理論と重なる部分もあって興味深いのですが、これまで自分で深く計算量の研究をしてきませんでした。学習理論の研究をしていると、サンプル計算量が主体なのですが、時間計算量や空間計算量も当然気になってはきます。ただ、そうやって全部入りの計算量を解析する話は、結局それぞれの計算量の深い研究の上にのっかるだけという感覚もあり、なかなか研究にするのは難しいなと思ってやめてしまったという経緯があります。
その上ディープラーニングが出てきて、計算アルゴリズムの技巧を駆使して計算量を減らすという話が学習研究の中では影をひそめてしまったという現状もあります。GPUを大量に駆使してお金に任せてぶんまわすという感覚が私にはついていけないので、少なくともその方面で研究することはないと思います。
