time complexity

Question

Find time complexity
 

int R(int n)  {
    if(n<=1)
        return 1;
    else       {
        int sum=0;
        for(int i=1;i<=n;i=i*2)
            for(j=1;j<=i;j=j*2){
                sum=sum+i;
                sum=sum*R(n/2);
                }
    }
    return sum;
}

Answer 1

Respected mam,

I am getting the time complexity as O(logn(log(logn))

but i am not confident.

Comments

Hi Pranay Datta 1

T(n) = (log n)² T(n/2) + c

can I apply master's theorem extended version here ( like a < b^k || a > b^k || a == b^k ) ?

Thanks in advance.

---

no, you can`t . "a" contains "n" a variable .

---

Hi Pranay Datta 1,

So , how can we solve in such cases ? 

Answer 2

i value	no of times ineer loop executes
1	1
2	2
4	3
8	4
n(let say it is 2^k=n)	k

each time inner loop executes R(n/2)  will be executed .let say its time complexiry is T(n/2)  then

no of times inner loop executes  = (1+2+3+4.................+k or log₂n)

                                               =logn(logn+1)/2

time complexity of this problem = (logn*(logn+1)*  T(n/2))/2   +  c

i dont know how to solve this recurrence .

Comments

soved the recurrence the complexity should be  0((log₂n)^2*log₂n)  or just   0((log₂n)^log₂n) 

is it correct???

Answer 3

For(int i=1;i<=n;i=i*2){
    For(j=1;j<=i;j=j*2){
        Sum=sum+i;
        Sum=sum*R(n/2);
    }
}  

First of all recursive call happens inside the inner loop, so solving will be difficult. Still, lets try. 

Outer loop runs $\log_2 n$ times and inner loop runs $\log_2 i$ times for each $i$ and $i$ is multiplied by $2$ after each iteration. So, the no. of times the inner loop runs will be 

$\lg 1 + \lg 2 + \lg 4 + \dots + \lg n \\= \lg \left(1.2.4.\dots. n\right) \\=\lg\left(2^0 . 2^1 . 2^2 . \dots 2^{\lg n}\right)
\\=\lg \left[ 2^{ \left ( 0 + 1 + \dots + \lg n\right)} \right]
\\= \frac {(\lg n). (\lg n + 1)}{2} $

So, our recurrence relation will be 

$T(n) = \frac{ (\lg n) .(\lg n + 1)}{2} T(n/2) + c$

Now, lets try substitution assuming $c = 1$.

T(1) = 1
T(2) = 2 
T(4) = 6
T(8) = 36
T(16) = 360
T(32) = 5400

I suppose all choices should be eliminated by now - the growth rate is higher than that of $n^2$. 

#include<stdio.h>  
int count = 0;
int R(int n)  {
    if(n<=1)      {
        count++;
        return 1;
    }
    else      {
        int sum=0,i,j;
        for(i=1;i<=n;i=i*2)
            for(j=1;j<=i;j=j*2){
                sum=sum+i;
                count++;
                sum=sum*R(n/2);
            }
        return sum;
    }
}
int main(int argc, char* argv[])  {
    R(atoi(argv[1]));
    printf("count = %d\n", count);
}  

Comments

thank you....

---

You are welcome :)

But is the time complexity exponential?

---

i think so..

---

It's actually ((lg n)!)^2/n. Can try solving by expanding.