2 / 4 Constant Factors & The Real Machine

Two Hundred Million Operations

A problem gives n≤2×105n \le 2 \times 10^5 and a 2 second limit. Budget 10810^8 simple operations per second, so 2×1082 \times 10^8 total. Note that log⁡2(2×105)≈17.6\log_2(2 \times 10^5) \approx 17.6 and 2×105≈447\sqrt{2 \times 10^5} \approx 447.

More than one candidate below fits. Select every one that does.

A

nn≈8.9×107n \sqrt n \approx 8.9 \times 10^7

B

n2=4×1010n^2 = 4 \times 10^{10}

C

nlog⁡2n≈3.5×106n \log_2 n \approx 3.5 \times 10^6

D

nlog⁡22n≈6.2×107n \log_2^2 n \approx 6.2 \times 10^7

E

n2/64≈6.3×108n^2 / 64 \approx 6.3 \times 10^8