(10 points) True/False Questions. Suppose that we have an algorithm A1 that runs

Question

(10 points) True/False Questions. Suppose that we have an algorithm A1 that runs in polynomial time, with a very large exponent, e.g. on input of size n it takes theta(n^1,000,000,000). Suppose further, that there is another algorithm A2 that runs in exponential time, with a base very, very close to 1, e.g. 0(1.00000000001^n). Justify your answers. You may use previous results from the lecture or this homework in your justification. You will not receive any credit unless your answers are correctly supported. True False For any arbitrary input, the running time of A1 will be smaller than the running time of A2. True False For large enough input, the running time of A2 will be larger than the running time of A1.

Explanation / Answer

False

A2 has a running time of 1.00000001n which for very large inputs will be close to 1 but for A1 it will increase rapidly with increasing value of n.

So A2 is much faster than A1

False

The running time of A2 will always be smaller than A1 for large inputs. Running time of A2 will be almost equal to 1.

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

---

---

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