What is polynomial time? I was readingTime complexity, it says that addition and multiplication are done in polynomial time without any explanations. Can somebody give a detailed proof why this is the case?
Thank you
 A: It means that the steps you need to solve a problem (and thus the amount of time you need) is some polynomial function of its size:
$ S = f(N) $
Polynomial functions are functions that involves $N$ or $N^2$ or $N$ to other powers, like:
$5N^8+2N^5+10N^2+..$ But important, it's not exponential functions like $ 2^N$ 
Because that makes the amount of steps you need to solve a problem very big very quickly.
Typical problems are multiplication and mazes. 
In contrast, consider the travelling sales man problem: https://en.wikipedia.org/wiki/Travelling_salesman_problem
The steps to solve this problem (finding the optimal route) is not a polynomial function of the amount of cities (size). 
A: Let us consider two numbers $a,b$ consisting of $N$ digits, that is:
$$a = a_Na_{N-1}....a_1 \\
b = b_{N}b_{N-1}...b_1.$$
How can we compute $c=a+b$? Well, we need to add the digits together:
$$c_1 = a_1 + b_1 \text{ mod } 10 \\
c_2 = a_2 + b_2 + r_2 \text{ mod } 10 \\
... \\
c_{N+1} = r_{N+1}.$$
Where I define the $r_n$ as the carryover of the previous calculation (so $r_n = \left(a_{n-1}+b_{n-1} - c_{n-1}\right)/10$).
If we assume that adding two digits together $\mathcal{O}\left(1\right)$ time (so we count time in however long it takes us to add digits) - can you figure out how many of these calculations we need to do in the worst case?
After you know how many, how does this number scale with $N$? 
Similar decomposition in terms of digits can be used to understand the scaling of multiplication too.
A: To add, it suffices to read & add the facing digits once from least to most significant, with possible carries. As these operations take constant time, addition is performed in linear time wrt the number of digits. This is optimal.
To multiply, you multiply & add the multiplicand as many times as there are digits in the multiplier. Hence quadratic time. This is suboptimal.

To add, you can increment the addend as many times as the value of the adder. This takes time exponential in the number of digits.
To multiply, you add the multiplicand as many times as the value of the multiplier. This also takes exponential time.

On a processor ALU, additions and multiplications both take constant time.
A: Let's first assume a machine or person that does multiplication of digits just as fast as they can add them. then we have $n$ digit multiplies for each of $n$ digits when multiplying 2 n digit numbers, and we have roughly the same number of adds, and a few more carries that don't mean much.  This means we have roughly $2n^2$ multiplies and adds the factor of two will be dwarfed by n as it grows meaning it won't exceed $n^3$ for long ( in fact not past $n=2$) and so it can basically be forgotten. Each operation takes the same amount of time, implying about as fast as we can do $n^2$ of these operations we can figure out multiplying two $n$ digit numbers. $n^2$ is a polynomial; Therefore, this is an example of polynomial time. 
