Estimating the bit operations using big O notation Using big- O  notation estimate in terms  of a simple function of $ n $ the number of  bit  operations required to compute $3^n$  in binary.
I need some help with the above question. The number of bit operations required to multiply two k- bit numbers is $O(k^2)$.
In the first step I am multiplying two 2-bit numbers, in the 2nd step a 4-bit and a 2-bit number and so on.
So the total bit operations will be I feel
$O(k^2) + O(k^2 * k) +.... + O(k^{n-1} * k)
\,\,with \,\, k \,= 2 $
How will the above sum be estimated as a function of n?
There are several problems. First, the time complexity of multiplying two k-bit numbers is much less than O(k^2). More like O(k log k). Since this is an important open research problem, you usually assume it is O(M(k)) for some function M and use that further.
Second, you are not multiplying two k bit numbers. You are multiplying one k-bit number by 3, which is done easily in O(k). This would get you a total of O(n^2).
Third, that’s not a clever method to calculate $3^n$. Much better is repeated squaring/multiplying. For example to calculate $3^{100}$: Start with 3, square, multiply by 3, square, square, square, multiply by 3, square, square. Since the number of bits starts small and doubles every time, this works in O(M(n)).