>>70 行列のノルムは↓の「行列ノルム - Wikipedia」が詳しいです。
http://ja.wikipedia.org/wiki/%E8%A1%8C%E5%88%97%E3%83%8E%E3%83%AB%E3%83%A0

n×n行列Pのij成分を出す計算量はO(1)、その行列の全成分の総和の計算量はO(n^2)
かと個人的に感じました。