mid exam

Question

Hi everyone.
I’ve gone through this two issues and solved them, please correct me if something looks wrong.
thanks.

sum1=0

for(k=1; k<=n; k*2)

for(j=1; j <= n; j++)

sum1++;

Sigma from k=1 to n/2 sigma from j=1 to n (1) = Sigma from k=1 to n/2 (n)= n/2 * n = n^2/2

 

sum2=0;

for(k=1;k<=n;k*=2)

for(j=1; j<=k; j++)

sum2++;

 

(n/2(n/2-1))/2=((n^2/4)-(n/2))/2=(n^2-2n)/n

Comments

in first question if n=8 then n/2 =4

=> k runs for k=1,k=2,k=4,k=8 i.e. 4 times....its correct

but if n=16 then n/2 = 8

=> k runs for k=1 , k=2 ,k=4, k=8 , k=16 i.e. only 5 times ...this is wrong.

so instead of  n/2 it should be log n + 1 times.

Answer 1

ans 1.

sum1=0;

for(k=1; k<=n; k*2).....//it executes log n + 1 times

for(j=1; j <= n; j++)....// it executes n times for each iteration.

sum1++;

------------------------------------------------------------------------------------------------------------------------

n	k ( executes log n + 1 times)	j (executes n times for each iteration)
1	1	1
2	1,2 i.e. 2 times	(1,2) , (1,2)
4	1,2,4 i.e. 3 times	(1,2,3,4) , (1,2,3,4) ,(1,2,3,4)
8	1,2,4,8 i.e. 4 times	(1,2,3,4,5,6,7,8), (1,2,3,4,5,6,7,8), (1,2,3,4,5,6,7,8), (1,2,3,4,5,6,7,8)
...	............................	......................
n	logn + 1 times	n times for each iteration

T.C. = O(no. of times outer loop executes * no. of times inner loop executes for each outer loop iteration)

       = O((log n + 1) *n)

       = O(n log n)

---------------------------------------------------------------------------------------------------------------------------------------------------------

 

ans 2.

sum2=0;

for(k=1;k<=n;k*=2)....// it executes log n + 1 times

for(j=1; j<=k; j++)...// it executes k times.

sum2++;

n	k ( executes log n + 1 times)	j (executes k times for each iteration)
1	1	1 i.e. 1 time
2	1,2 i.e. 2 times	(1 ), (1,2 ) i.e 3 times
4	1,2,4 i.e. 3 times	(1) , (1,2) , (1,2,3) i.e. 6 times
8	1,2,4,8 i.e. 4 times	(1) , (1,2) , (1,2,3) , (1,2,3,4) ... 10 times
...	............................	......................
n	logn + 1 times	(1) , (1,2) , (1,2,3) , (1,2,3,4) ... (1,2,3,4,..k) i.e. k(k+1)/2 times

T.C. =  O$\left ( \frac{k*(k+1)}{2} \right )$ 

       = O$\left ( \frac{(log n + 1)*( log n + 1 +1)}{2} \right )$ 

       = O( log n * log n )

Comments

Bro! I think the answer for 2nd qstn is 0(n^3).

U are taking k is different in both the loops but i think they are nested loops with respect to k.

So it runs as 1+2+4+8.......+2^n

So answer is 0(n^3).

---

@d.bhavani shankar

can u explain where am i going wrong.

1+2+4+8...+$2^{n}$ are the outputs that are produced in $1^{st},2^{nd},3^{rd},4^{th},...log(n+1)^{th}$ execution of k loop and not the time it executes.

and for each value of k, $j$  loop runs for $\left ( \frac{k*(k+1))}{2} \right )$ times as i have shown. this makes both loops to run according to k.