Big-O notation basic

Computer Science Level 2

One day your friend who has a tendency of lying on pretty much everything came up to you made the following three claims:

$\begin{aligned} &(A) &\quad (n+k)^{ x }\quad &=&O(n^{ x }) \\ &(B) &\quad 2^{ 2n+1 }\quad &=&O(2^{ n }) \\ &(C)& \quad{ 2 }^{ n+1 }\quad &=&O({ 2 }^{ n }) \end{aligned}$

For constant $k$ and $x$ , which of the statements is actually true?

A

and

C

A

B

and

C

A

and

B

B

and

C

1 solution

Geoff Pilling
Feb 3, 2017

For (A):

$(n+k)^x \to n^x$ for large $x$ $\implies O(n^x)$

For (B):

$\quad 2^{ 2n+1 }\quad \to 2 ]cdot 2^{2n}$ $\implies O(2^{2n})$

For (C):

$\quad{ 2 }^{ n+1 }\quad \to 2 \cdot 2^n$ $\implies O(2^{n})$

So, only $\boxed{\text{A and B}}$ were correct.

Big-O notation basic

1 solution

0 pending reports