as a function of $N$ while running the code on my own laptop. The time increases linearly with

the number of digits, so in Big O notation, its performance can be written as $O(N).$

f$)$ Using time module of Python, evaluate the algorithmic efficiency of your code in part d$.$

You need to make the similar figure shown above on your computer.

g$)$ How long will running your code for $N={10}^7$ take? You do not run your code for this

big number of digits! Use extrapolation to estimate the running time. Do you think we need

to improve the performance of our code to execute it for large numbers?

Let's improve the performance of the code. We can express any number in the base$-2$ numeral

system $("0"$ and $"1").$ Any decimal number can be expressed with a series of zeroes and ones $(a_i)$ :

Decimal number $={\displaystyle \underset{?}{\overset{?}{}}}{a}_i{2}^i$

For example, $22=12^4+02^3+12^2+12^1+02^0.$ So$,22$ in the binary system is $10110.$

h$)$ Write your own function which takes a decimal number and return the number in the

binary system. Do not use bin$()$ syntax of python.

In part b$,$ you derived that $(N)=A^{N-1}(1),$ so writing $N-1$ in the binary system,

$N-1={\displaystyle \underset{?}{\overset{?}{}}}{a}_i{2}^j,$ we get:

$(N)=A^{N-1}(1)=A^{{\displaystyle \underset{?}{\overset{?}{}}}{a}_j{2}^j}(1)=(A^{2^j}{)}^{a_j}(1)=$dots$(A^4{)}^{a_2}(A^2{)}^{a_1}(1)$

For clarity if we want to find $(23),$ it can be explained as follows: