Problem 4 (100 points) 4.1 Implement loops a – f in Problem 3.1 and show heurist

Question

Problem 4 (100 points)

4.1 Implement loops a – f in Problem 3.1 and show heuristically that runtime grows according to Big-O for each set of loops.

4.2 Show heuristically that runtime grows according to your estimation of Big-O for each GCD algorithm in Problem 2.7.

4.3 A. Develop and implement a Fibonacci function that does not use recursion. B. Find Big-O of your function. C. Run an experiment that compares the times with your recursive function. D. Heuristically show that both Fibonnacci functions perform as predicted by their Big-O estimates

Explanation / Answer

Answer

4.1

a.    sum = 0;

for (int i = 0; i < n; i++)

sum++;

As, there is only one loop that will run for n number of times, the runtime for this loop will be BigO(n). So, as n will grow BigO(n) will also increase and vise-versa.

b.

sum = 0;

for (int i = 0; i < n; i++)

for (int j = 0; j < n; j++)

sum++;

As, there are two loops(one within the other) that will run for n*n number of times, the runtime for this loop will be BigO(n^2). So, as n will grow BigO(n^2) will also increase and vise-versa.

c

sum = 0;

for (int i = 0; i < n; i++)

for (int j = 0; j < n * n; j++)

sum++;

As, there are two loops(one within the other) that will run for n*(n*n) number of times, the runtime for this loop will be BigO(n^3). So, as n will grow BigO(n^3) will also increase and vise-versa.

d.

sum = 0;

for (int i = 0; i < n; i++)

for (int j = 0; j < i; j++)

sum++;

As, there are two loops(one within the other) that will run for n*(0+1+2+3+...+(n-1)) number of times, the runtime for this loop will be BigO(n^2). So, as n will grow BigO(n^2) will also increase and vise-versa.

e.

sum 0;

for (int i = 0; i < n; i++)

for (int j = 0; j < i * i; j++)

for (int k = 0; k < j; k++)

sum++;

As, there are three loops(one within the other) that will run for n*(0^2+1^2+2^2+3^2+...+(n-1)^2)*(0^2+1^2+2^2+3^2+...+(n-1)^2) number of times, the runtime for this loop will be BigO(n^4). So, as n will grow BigO(n^4) will also increase and vise-versa.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

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