How to prove or disprove: 1) 2^(n+1)=O(2^N); 2) 2^2N != O(2^n)?

Question

Mathematics

https://www.daniweb.com/programming/computer-scien... - there are approximate explanations here, but no exact solution

Answer 1

Как доказать или опровергнуть

Use the definition:
2^(n+1)=O(2^N) означает, что найдётся x0 и M, такие, что для любого x > x0, 2^(x+1) < M * 2^x. Деля обе части на положительное 2^x получаем 2 < M. Т.е. оно справедливо для любого x0 и M > 2.

Answer 2

Substitute 1, 2, ... 10 and check)
More strictly, divide the left side by the right side, take the limit as N -> to infinity. If equality is preserved (1 = 1), then true:
1. True, for large N: (N + 1) / N = 1
2. Верно, при любом N: 2^2N / 2^N = 2^N != 1