# Logarithms and big O notation

Recall the equivalence: $$m=2^k \implies k=log_2m$$ (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-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-O notation.

i am totally confused about this question, can someone please walk me through this problem or give me a nudge in the right direction, (also where does the n come from?)

-
Well, the problem itself states that you are trying to come up with the answer in terms of $n$. Can you see how in each problem, $k$ depends on $n$? –  Dennis Meng Oct 2 '13 at 5:19
no, how do i get started on this problem? –  notamathwiz Oct 2 '13 at 6:02
If you can't answer my question, you're definitely not going to be able to get started on this problem. –  Dennis Meng Oct 2 '13 at 6:03
does that mean we change the k to n and write our answer in terms of n? –  notamathwiz Oct 2 '13 at 6:06
No, you do not change $k$ to $n$, but yes, your answer is going to be in terms of $n$. –  Dennis Meng Oct 2 '13 at 6:09

$n$ is just another variable.

This is really just a compound problem: you need to break it into parts and solve the parts.

For example, one part of the first problem could be

Find a formula for the general term of the sequence given by $a_1 = 1$, $a_{u+1}=2a_u$

(I changed the dummy variable because it doesn't matter, but it might help eliminate confusion between this part and the rest of the problem)

(I say 'could be', because this is just one approach to the problem)

-
would the general sequence of the first one be $a_k=2a_{k-1}$?? –  notamathwiz Oct 2 '13 at 6:19
can someone please explain what n is supposed to represent –  notamathwiz Oct 2 '13 at 6:53
$n$ is supposed to represent $n$, the variable integer appearing on the right hand side of the equation $a_k \geq n$. –  Hurkyl Oct 2 '13 at 6:58
... that you're supposed to solve for $k$ in terms of $n$. (and find the minimum solution) –  Hurkyl Oct 2 '13 at 7:35