big Oh notation of the smallest k

Question

Recall the equivalence: $$m = 2^k , k = \log_2 m$$

(a) Consider the sequence: $$a_1 = 1; a_{k+1} = 2a_k$$ What is the smallest $k$ for which $a_k \geq n$? Your answer should be a function of $n$, and you can leave it in big-$\mathcal{O}$ notation.

(b) Consider the sequence: $$a_1 = 2; a_{k+1} = a_k^2$$ What is the smallest $k$ for which $a_k \geq n$? Your answer should be a function of $n$, and you can leave it in big-$\mathcal{O}$ notation.

---

Solutions:

(a) We have $a_k=2^{k-1}$. The first time this exceeds $n$ is when $k$ is roughly $\log n$.

(b) We have $a_k=2^{(2^{k-1})}$. This first exceeds $n$ is when $2^{k-1}$ exceeds $\log n$, that is, when $k$ is roughly $\log \log n$

---

can anyone please help me understand the problem above. I do not understand for part $a$ how they got $2$ to the power of $k-1$, how did they know to use $k-1$ as the exponent and why do they use that exponent here. also how do i get to the solution for $\log n$ and $\log \log n$.

Answer 1

For part (a), notice $$ a_k = 2a_{k-1} = 2^2 a_{k-2} = \ldots = 2^{k-2}a_2 = 2^{k-1}a_1 = 2^{k-1}. $$ You can prove this formally by induction.

You now want to find $k = k(n)$ such that $a_k = 2^{k-1} \geq n$. Thus $2^k \geq 2n$ and $$ k = \log_2 2^k \geq \log_2 2n = \log_2 n + \log_2 2 = \mathcal{O}(\log_2 n). $$

Similarly, for part (b) $$ a_k = a_{k-1}^2 = a_{k-2}^4 = a_{k-2}^{2^2} = (a_{k-3}^2)^{2^2} = a_{k-3}^{2\cdot 2^2} = a_{k-3}^{2^3} = \cdots a_2^{2^{k-2}} = a_1^{2\cdot 2^{k-2}} = 2^{2^{k-1}}. $$ Again it's easy to prove this formally by induction.

You can determine the size of $k$ in a similar fashion here.

---

Edit: In your comment, you said

i dont understand the "..." (steps you skipped) how you got to the final answer

The short answer is: I applied the recursive definition of $a_n$ to $a_k$ (and then $a_{k-1}$, and so on) until I saw the general pattern. While "how did you see the general pattern?".

Let's return to part (a). If you're new to this, probably the easiest way to identify the pattern here is to keep applying the recursive definition of $a_n$ to write $a_k$ as $$ a_k = 2^1 a_{k-1} = 2^2 a_{k-2} = 2^3 a_{k-3} = 2^4 a_{k-4}. $$ At each step we have that $a_k = 2^m a_{k-m}$, and it's easy to see from the definition of $a_n$ that this pattern will continue until we get to $a_k = 2^{k-1} a_1$, which is just $2^{k-1}$.

As I suggest in my original answer, this is in no way a formal proof that $a_k = 2^{k-1}$; in fact we're forming a conjecture about what $a_k$ should equal. Now that we think $a_k = 2^{k-1}$, we should prove that this is the case by induction. Try this.

A similar explanation applies regarding how to find the pattern for part (b).

Answer 2

Find some $k$ with respect to $n$ means you need to roughly solve the recursive relation. Obviously, (a) is a geometric progression series and has the form $a_k=c\cdot2^k$ for some constant $c$ depending on $a_1$. Then solving $k$ from $n=a_k$ gives an approximate value. For part (b), letting $b_n=\log a_n$ transforms to case (a).