Asymptotic Complexity of a code fragment The following code fragment is a Monte

Question

Asymptotic Complexity of a code fragment

The following code fragment is a Monte Carlo method for approximating Pi (for more background, see the link
http://mathfaculty.fullerton.edu/mathews/n2003/montecarlopimod.html). The method calculates a random point
in a unit square, and then checking if the point is inside the radius of a unit circle. The probability that a random
point will be inside the circle is proportional to the area of the circle. This algorithm only considers one quadrant of
the circle, so we multiply the result by 4 to get an approximation for Pi. It

Explanation / Answer

i = 0 ------------1 step
count = 0 ----------- 1 step
while(i<n) ----------- n+1 step
x = random() ----------- n*1 steps
y = random() ----------n*1 steps
if (x^2 + y^2 <= 1) ------n*1 steps
count = count+1 -------n*1
i = i + 1 ----------- n + 1
done
pi = 4*count/n -----------> 1 step

2. The worst case would be when very few (x, y) will satisfy the condition (x^2 + y^2 <= 1) .

but in this case also total no of steps would be ~ O(np) given n is large

Only the value of pi will be lesser accurate.

3. The best case would be when more (x, y) will satisfy the condition (x^2 + y^2 <= 1) .

but in this case also total no of steps would be ~ O(np) given n is large

Only the value of pi will be more accurate.

4.One of the first schemes to lower the calculation time was to group the N zones into
p patches, and transfer power from patches to zones (elements) . Still, the computation time
will be at least O(Np), so many zones need to be grouped before a large savings occurs.

If p-> n (-> tends to)

It will change to O(n^2)

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

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