GoogleCodeJamのQualificationに参加してみて、
どのくらいまでのオーダーの計算量ならコンテスト中に処理できるのか
気になったので簡単なプログラムを作って計測してみました。

テストに使ったのはこんなコード。
ぐちゃぐちゃだけど気にしないで！

	public static void main(String[] args) {
		for (int order = 1; order <= 15; order++) {
			long start = System.currentTimeMillis();
			long temp = 0;
			long end = (long) Math.pow(10, order);
			for (long i = 0; i < end; i++) {
				if (i % 2 == 0) {
					temp -= i;
				} else {
					temp += i;
				}
			}

			long diff = System.currentTimeMillis() - start;
			System.out.printf("O(10^%d) %d:%02d.%04d\n", order, diff / 1000 / 60, diff / 1000 % 60, diff % 1000);
		}

	}

以下が出力結果ですー！

O(10^1) 0:00.0000
O(10^2) 0:00.0000
O(10^3) 0:00.0000
O(10^4) 0:00.0000
O(10^5) 0:00.0000
O(10^6) 0:00.0026
O(10^7) 0:00.0438
O(10^8) 0:04.0543
O(10^9) 0:46.0106
O(10^10) 7:43.0682

• O(10^7)までは計算量と時間に一応の相関関係はみえる。一応の。
• O(10^8)までがコンテストなら許容範囲かな？
• O(10^8)からは計算量と時間にはっきりと比例関係がみえる。
• O(10^5)まではミリ秒単位でもゼロ！改めてコンピュータの計算力って凄いね。

コンパイラのバージョンはjdk1.6でした。
もちろん計測するコンピュータによって結果が変わってくると思うので参考程度に使ってください。