Data Structure 1. Suppose that algorithm A takes 1000n 3 steps and algorithm B t

Question

Data Structure

1. Suppose that algorithm A takes 1000n 3 steps and algorithm B takes 2An steps (Note the carot symbol means raise to the power of which we use here becuase we cannot create the appropriate mathematical symbol in moodle) for a problem of size n. For what size of problem is algorithm A faster than B (meaning algorithm A has fewer steps than B)? In your answer describe not only what the answer is but how you arrived at the answer. 2. Give the upper bound (big O notation) that you can for the following code fragment, as a function of the initial value of n. for(int i = 0; i

Explanation / Answer

1. Algorithm A take 1000n^3 steps and Algorithm B take 2^n steps.

To determine the fastness of both these algorithms, it completely depends on the value of n. Consider n to be 1. In this case Algo A takes 1000 steps and Algo b takes just 2 steps to complete.

Increase the value of n to 100 now, Algo A takes 1000*(100)^3 which was 1,000,000,000.

Algo B takes 2^100 . Basically 2^10 =1024. So 2^100 is nothing but multiplying (2^10) 10 times= (1024)^10 which will be nearly equal to 10^30 whcih means this number has 1 followed by 30 zeros.

So as the value of n keeps on increasing the Algo A is very faster and very efficient. beacuse when we have 2^n or 3^n or some k^n. the n factor plays a very key role. It will increase very fastly and rapidly.When we have a high value of n, n^k is faster than k^n. Here k is a constant.

2. Here the outer for loop was taking n iterations, and the inner for loop value depends entirely on the outer for loop.

Which means for the value i=1, the inner for loop takes 1 step, whereas when the value of i=n, the inner for loop takes n times.

Sample example for this program is :

*

**

***

The upper bound says that is the best known time complexity and lower bound says you cant do better than that. For the above * example, we cannot do better than that. We need one loop for generating rows and other loop for genrating columns of that specific row. So the lower bound is likely to be same as the upper bound.

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

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