Need a detailed step by step explanation to solve this probl

Need a detailed step by step explanation to solve this problem.

Explain with pseudo code in python: compute 2^2n in linear time, assuming multiplication of arbitrary size integers takes a constant time operation. What is the bit-complexity If multiplications do not take constant time, but the multiplication takes O(n^2) time not O(1)

Solution

1-algorithm and rule for multiplying two numbers x and y is to create an array of intermediate sums, each representing the product of x by a single digit of y.

If x and y are both n bits, then there are n intermediate rows, with lengths of up to 2n bits (taking the shifting into account). The total time taken to add up these rows, doing two numbers at a time, is O(n) + O(n) + · · · + O(n) | {z } n 1 times , which is O(n 2 ),

2-The bit-complexity of multiplication

This s very open problem:-

Theorem (Schönhage & Strassen 1971) The product of two n-bit numbers can be computed in time O(n log n log log n).

O(n log n l)2

Theorem (Fürer 2009) Two n-bit integers can be computed in time O(n log n 2O(log n) ).