QA Software testing The algorithm below solves this problem https://projecteuler

Question

QA Software testing The algorithm below solves this problem https://projecteuler.net/problem=6 (Links to an external site.)Links to an external site.

a. Measure the performance of the algorithm.

b. Implement an algorithm that you believe will improve the performance.

c. Measure the performance of the new algorithm.

static void Main(string[] args) {

int N = 100; int sum = 0;

int sumsqr = 0; for (int i = 1; i <= N; i++)

{

sum += i; sumsqr += i * i;

}

int sqrsum = sum * sum;

int result = sqrsum - sumsqr;

Console.WriteLine("Result: " + result); Console.ReadLine(); } S

ubmit the timing of the algorithm in Ticks, the revised algorithm and it's time in ticks.

Explanation / Answer

Hello Student!

a) The algorithm that has been shown in the question suggests.

1. We need to calculate sum of squares of first n number.

So, if we do so.. what would time complexity look like -

Consider for 10 numbers -

sum = 0;

for i = 1 ; i <= 10 ; i++

sum = sum+ i*i;

end

cout << sum << endl;

Our loop run for n = 10. Therefore it will run for O(n) time complexity.

2. We need to calculate square of the sum

If we compute it.. the time complexity would look like -

For n = 10

sum = 0

for i = 1 ; i <= 10 ; i++

sum = sum + i

end

sum = sum*sum ;

cout << sum << endl;

Our loop run for n = 10. Therefore it will run for O(n) time complexity.

Now, if we combine the time complexity of the two methods it comes out to be O(n)+O(n) == O(n)

So, our algorithm will have a time complexity of O(n)

Part b) Implement an algorithm that you believe will improve the performance.

We know that sum of square of n numbers can be calculated as -

12 + 22 + 32 + .... + n2 = n*(n+1)*(2n+1)/6 eq(1)

and we also know that -

1 + 2 + 3 + .... + n = n*(n+1)/2

If we square both the sides

(1 + 2 + 3 + .... + n)2 = ( n*(n+1)/2 )2 eq(2)

Now, from the above link it is given that the difference between the sum of the squares of the first ten natural numbers and the square of the sum 2640.

Computing our result using eq(1) and eq(2)

eq(2) - eq(1) = 2640

Taking L. H. S

(n*(n+1)/2)2 - n*(n+1)*(2n+1)/6

For n = 10

(10*11/2)2 - (10*11*21/6)

(55)2 - (55*7)

3025-385

2640

Hence, L. H. S = R. H. S

Hence, our proposed algorithm is correct.

Part c) Measure the performance of the new algorithm.

New algorithm employees eq(1) and eq(2)

For computing the result for particular n value it will take constant time.

So, for any n value solving the problem it will take O(1) time.

Which is much more efficient than the previous algorithm discussed.

Thank you. Feel free to ask anything. Please upvote the answer. It means a lot. Thank you again.

Edited :

Algo 1 :

public static void Main()

{

DateTime dt = DateTime.Now;

Int64 dtStart = DateTime.Now.Ticks;

int N = 100; int sum = 0;

int sumsqr = 0;

for (int i = 1; i <= N; i++) {

sum += i; sumsqr += i * i;

}

Int64 dtEnd = DateTime.Now.Ticks;

Int64 result = dtEnd-dtStart;

Console.WriteLine("Total Ticks: "+ result);

}

Algo 2 :

public static void Main()

{

DateTime dt = DateTime.Now;

Int64 dtStart = DateTime.Now.Ticks;

int N = 100; int sum = 0;

int sumsqr = 0;

sum = N*(N+1)*(2*N+1)/6;

sumsqr = N*(N+1)/2;

sumsqr = sumsqr*sumsqr;

Int64 dtEnd = DateTime.Now.Ticks;

Int64 result = dtEnd-dtStart;

Console.WriteLine("Total Ticks: "+ result);

}

Number of ticks are dependent upon the compilation but the second algo gives lesser ticks in most of the cases.

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

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