ace test 4

Question

ans given is option A

Comments

WITH RECURRENCE RELATIONS

answer is O( sqrt(n)*log(n) )

FOR INNER LOOP:

as the sequence goes 1 -> 3 -> 6->10 ->15 -> 21 ->.  ......... -> N

suppose there are k terms and a(k)=N;

so as from pattern we can see kth term can be written as  a(k)=a(k-1)+k   || base condition is a(1)=1(i.e first term is 1)

solving recurrence relation=

a(k)=a(k-1)+k

      =a(k-2)+k-1+k

      =a(k-3)+(k-2)+(k-1)+k

.

.

.

   =  a(k-m)+{k+(k-1)+(k-2)+(k-3)+........+(k-m+1)}

   = applying base condition i.e. k-m=1

  =a(1)+{k+(k-1)+(k-2)+(k-3)+........+3+2}.           ||as a(1)=1

 

    =1+2+3+4+5+........+(k-2)+(k-1)+k

N=(k(k+1))/2.  

so k is equivalent to sqrt of N

as k is the number of terms in above sequence so inner loop will run O(sqrt(n)) times

so for each outer loop 1 iteration the inner loop will run for O(sqrt(n)) times

so program complexity will be  O(sqrt(n)*log(n))

---

But the inner loop is not running exactly or less than  sqroot(n) times everytime , for an instance for n=64 , the inner loop runs for 10 times , which is greater than sqroot(64) which is 8 . So it can written as Omega(sqroot(n))  but not O(sqroot(n)) since Big-Oh shows the upper bound but the loop is actually running more than sqroot(n).

---

Yeah correct prashant jha 1  check my solution 

Answer 1

This is what I think should be the answer.