Suppose that you have two different algorithms for solving a problem. To solve a

Question

Suppose that you have two different algorithms for solving a problem. To solve a problem of size n. the first algorithm uses exactly n^2 2^n operations and the second algorithm uses exactly n! operations. As n grows, which 1. algorithm uses fewer operations? Given a real number x and a positive integer k. determine 2. the number of multiplications used to find x^2^k starting with x and successively squaring (to find x^2, x^4, and so on). Is this a more efficient way to find x^2^k than by multiplying x by itself the appropriate number of times?

Explanation / Answer

SOLUTION 1:

In the two algorithms of size n, the Second Algorithm takes more operations when compared to First algorithm.

for example:

if n=3

First algorithm gives 72

Second algorithm gives 6

if n=4

First algorithm gives 256

Second algorithm gives 24

if n=10

First algorithm gives 102400

Second algorithm gives 3628800

Similarly when the size of n increases the number of operations in second algorithm increases

SOLUTION 2:

In this question the number of multiplications depend on k value.

for example:

if k=2;

the answer will be x^4 which takes 2 operations i.e., x.x=x^2

x^2.x^2=x^4

if k=5;

the answer will be x^32 which takes 5 operations i.e.,

x.x=x^2

x^2.x^2=x^4

x^4.x^4=x^8

x^8.x^8=x^16

x^16.x^16=x^32

This is quite efficiet as the number of operations completely depend on k value

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.