Question

Prove that $\mathbf{TIME}\mathbf{(}{\mathbf{2}}^n\mathbf{)}\mathbf{=}\mathbf{TIME}\mathbf{(}{\mathbf{2}}^{n+1}\mathbf{)}$

Short answer

The problem can be solved by using Big-O notations which is on the basis of the minimum time required by the most efficient algorithm to determine upper and lower bounds, the classification of computation time can be done.

Step-by-step solution

Using Big-O notations

Big-O notation is usually used to define the lower and upper bond which hides smaller terms and constant factors.

Therefore, in Big-O notations the time complexity of thefunction${\mathbf{2}}^{\mathbf{n}\mathbf{+}\mathbf{1}}$ is${\mathbf{2}}^{\mathbf{n}}$

Coming to the conclusion of the given problem.

The problem can be solved by using Big-O notations which is on the basis of the minimum time required by the most efficient algorithm to determine upper and lower bounds, the classification of computation time can be done.

From the above explanationWe understood that$A\in \text{TIME}\left(2^n\right)$if and only if$A\in \text{TIME}\left(2^{n+1}\right)$

Hence, .$\text{TIME}\left(2^n\right)=\text{TIME}\left(2^{n+1}\right)$