algorithmsasymptotics
When it comes to algorithms, you frequently have to evaluate problems like this:
Let $x$ be an $n$-bit integer. For each of the following questions, give your answer as a function of $n$.
Or a question like this:
[given algorithm] Assume that the subtraction takes $O(n)$ time on an $n$-bit number.
What does "let $x$ be an $n$-bit integer" really mean? It is just the amount of bits reserved for a random int variable $x$?
How does the $n$-bit number relate to the big $O$ of $n$ notation?
Your translation is correct. The intuition behind big-oh notation is that $f$ is $O(g)$ if $g(x)$ grows as fast or faster than $f(x)$ as $x \rightarrow \infty$. This is used in computer science whenever studying the time complexity of an algorithm. Specifically, if we let $f(n)$ be the run-time (number of steps) that an algorithm takes on an $n$ bit input to give an output, then it may be useful to say something like $f$ is $O(n^2)$, so we know that the algorithm is relatively fast for large inputs $n$. On the other hand, if all we knew was $f$ is $O(2^n)$, then $f$ might run too slowly for large inputs.
Note I say "might" here, because big-oh only gives you an upper bound, so $n^2$ is $O(2^n)$ but $2^n$ is not $O(n^2)$.
Given a positive integer $n\in\textbf Z^+$, consider the list $$1,2,3,...,n$$ comprised of the first $n$ positive integers. You have to guess some positive integer $1\leq x\leq n$ contained somewhere in this list, and whenever you make a guess, you are told one of three things $$1.\text{Your guess is too high :(}$$ $$2.\text{Your guess is too low :(}$$ $$3.\text{Your guess is correct!}$$ How can you guess what $x$ is? Let me go over two possible strategies. The first one is called linear search. Basically, what you do is guess that $x=1$, and if you get it correct then you celebrate and go drink a lot of beer, while if you are told that $1$ is too low, then you guess the next number in the list, i.e. you guess $x=2$, and if this is correct then you celebrate and go drink a lot of beer, while if you are told that $2$ is too low, then you guess the next number $3$, and this process keeps repeating until you guess the correct number (and go celebrate and drink a lot of beer). For each positive integer $n\in\textbf Z^+$, I'm going to let $T_{\text{linear}}(n)$ denote the maximum number of guesses that you need to correctly guess what $x$ is in a list of length $n$ using the linear search algorithm described above. Convince yourself then that the following table of values is indeed accurate: \begin{array}{r|c} n & T_{\text{linear}}(n) \\ \hline 1 & 1 \\ 2 & 2 \\ 3 & 3 \\ 4 & 4 \\ 5 & 5 \\ 6 & 6 \\ 7 & 7 \\ 8 & 8 \\ 9 & 9 \\ \vdots & \vdots \end{array} In short, for all positive integers $n\in\textbf Z^+$, $T_{\text{linear}}(n)=n$.
Now let's consider another strategy called binary search. Here, you start by guessing that $x$ is the "middle term" in the list, say $x=n/2$ if $n$ is even and $x=\frac{n+1}{2}$ is $n$ is odd. If the guess is correct, then you're done, while if the guess is too low then you have basically eliminated $\approx 1/2$ of the possibilities for what $x$ could be, and then you just apply the whole procedure again to the remaining half of the list, and you keep doing this until you guess correctly. For each possible list length $n\in\textbf Z^+$, let $T_{\text{binary}}(n)$ denote the maximum number of guesses that you need to correctly guess what $x$ is in a list of length $n$ using the binary search algorithm described above. In this case, convince yourself that the following table of values is correct:
\begin{array}{r|c} n & T_{\text{binary}}(n) \\ \hline 1 & 1 \\ 2 & 2 \\ 3 & 2 \\ 4 & 3 \\ 5 & 3 \\ 6 & 3 \\ 7 & 3 \\ 8 & 4 \\ 9 & 4 \\ \vdots & \vdots \end{array}
and that in general, for all positive integers $n\in\textbf Z^+$, we have that $T_{\text{binary}}(n)=\lfloor\log_2(n)\rfloor+1$. Below in red is the graph of the $T_{\text{linear}}$ function while in green is the graph of the $T_{\text{binary}}$ function:
Overall, it is clear that binary search is a much more efficient algorithm than linear search when it comes to this particular task of guessing a number in a list, especially as the list gets larger and larger (i.e. as $n\to\infty$). Computer scientists will often say that linear search runs in at worst $O(n)$ time (or linear time), while binary search runs in at worst $O(\log(n))$ time (or logarithmic time). This is because, using the notation from the original post, we have $X=\textbf Z^+$, $f(n)=T_{\text{linear}}(n)=n$ or $f(n)=T_{\text{binary}}(n)=\lfloor\log_2(n)\rfloor+1$, and $g(n)=n$ or $g(n)=\log(n)$ respectively, since in the first case we can choose $c:=1$ and $M:=1$ for instance, while in the latter case we can choose $c:=5$ and $M:=4$.
Best Answer
We usually represent numbers as finite sequence of digits. In base-$2$ each digit is called bit and has value $0$ or $1$. So we write each number $a$ as $\sum_{k=0}^n a_i2^i$, where $a_i$ are digits and assuming $a_n\neq0$ number $a$ is called $n$-bit number. Notice that if $a$ is $n$-bit number then $2^{n-1}\leq a<2^n$. So number of bits of number $a$ is $O(\log a)$.
If algorithm works on individual digits, then the complexity is dependant on length of given number (by length I mean number of bits). For instance how does addition algorithm works? You want to add $a$ and $b$, first you add $a_0$ and $b_0$, write down the result, if necessary carry $1$, continue for next bit and so on. As a result you do $n$ bit additions, so adding two $n$-bit numbers has complexity $O(n)$.
So basicly, saying that algorithm takes time $O(n)$ for $n$-digit number, means that it is linear with respect to the length of given number. And also that it takes time $O(\log n)$ with respect to the number itself.