Complexity analysis

[Rave]

well i need to find the T(n) for this:

int recursive(int n) 
{
    int x,y;
    if (n <= 1) return 0;
    else
    {
    for (int i=0; i < n ; ++i) O(1);
    recursive (n/2);
    recursive (n/2);
    }
}

i said  T(n)=Constant+n*n*log(n);

i am not so sure about it, am i correct?

[ne555]

for (int i=0; i < n ; ++i)
  O(1); // <-- What is this line? 

Is the recursive call inside the for loop? If yes, then

 T(n) = n*T(n/2) 

[Rave]

the O(1), means something of order one is being executed, example cout,
but i need it to be solved in terms of n,

[m4ster r0shi]

Well, I guess we can say that for (int i=0; i < n ; ++i) O(1); is O(n).

Now,

T(n) = 2*T(n/2) + O(n)
T(n) = 2*(2*T(n/4) + O(n/2)) + O(n)
...
T(n) = 2k*T(1) + sum(i=0 -> k-1) of (2i*O(n/2i)), where k=log2n
T(n) = 2k*T(1) + k*n*O(n)
T(n) = O(n) + O(n2logn)
T(n) = O(n2logn)

EDIT: Correction...

So, yes, you are probably right.

EDIT 2: No, wait...

The master theorem (case 2) doesn't agree with us... -> http://en.wikipedia.org/wiki/Master_theorem#Case_2

[m4ster r0shi]

Ok, I found my mistake... In calculating the complexity of the sum above, I took a very big bound.
It can be smaller:

sum(i=0 -> k-1) of (2i*O(n/2i)) = O(n) + 2*O(n/2) + 4*O(n/4) + ... + 2k-1*O(n/2k-1)

Each one of the terms is O(n) and there are k (=log₂n) terms,
so, the complexity of the sum is k*O(n) = O(nlogn),
which also gives a total complexity of O(nlogn).