find the Big-Oh Notation or the cost of: (a)sum = 0; for(i=0;i<sqrt(n)/2;i++) su

1) (a) O(n^1/2) (b) O(n^1/2) (c) O(n^5) (d) O(n^5) 2) The time for n=400 will be 20ms.

ID: 3784761 • Letter: F

Question

find the Big-Oh Notation or the cost of:

(a)sum = 0;
for(i=0;i<sqrt(n)/2;i++)
sum++;
for(j=0 ;j<sqrt(n)/4;j++)
sum++;
for(k=0;k<8+j;k++)
sum++;

(b)sum = 0;
for(i=0;i<sqrt(n)/2;i++)
for(j=i;8+i;j++)
for(k=j;k<8+j;k++)
sum++;

(c)sum = 0;
for(i=1;i<2*n;i++)
for(j=1;j<i*i;j++)
for(k=1;k<j;k++)
if (j % i == 1)
sum++;

(d)sum = 0;
for(i=1;i<2*n;i++)
for(j=1;j<i*i;j++)
for(k=1;k<j;k++)
if (j % i)
sum++;

2. If it takes 10ms to run program (b) for n=100, how long will it take to run for n=400 ?

1)
(a) O(n^1/2)
(b) O(n^1/2)
(c) O(n^5)
(d) O(n^5)

The time for n=400 will be 20ms.

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