algorithms

Question

int recfunc(  int n )

2  { if( )

3  return n;

4  int i=0;

5   while(i<100){

6  printf ("HELLO");

7  i=i+1;

}

8  int a;

9  a=2* recfunc(n/2);

10   while(j<a){

11   printf("BYE !");

12   j=j+1;

}

13  return a;

}

what is  the recurrence relation for this?

Comments

what is j?

---

j is a variable

---

i mean what is initialization of j?

---

j=o

---

R(n) = R(n/2) + O(n/2)

---

or rather its O(n) instead of O(n/2)

is this O(n) term because of while loop

---

yes..

---

Shaik Masthan Shouldn't it be R(n) = R(n/2) + thetha(n)?

The while loop runs through 0 to a-1 = a iterations in total

And if we check the value of a for some values of n, a refunc(n/2) returns n/2

And 2* n/2=n.

So it should run for n/2 iterations and each iteration takes constant time.

 

Correct me if I am wrong.

---

but what about when n is odd , lets say n=5 so ,   5/2 =2. Thus instead of 2.5 , you will get only 4   as 2*(5/2=2) correct me if am wrong.

---

Shaik Masthan hitendra singh

Now I get it, its closer to thetha(n/2) when the number is odd. :-D

Thanks