help computing time complexity

[dirk_gently]

Hi all!
I'm having some trouble computing the time complexity of the following code:
(A and B are doubles greater than 1)

void do(int n) {
   if (n<=1) return;
   print(n);
   do(n*A/(A+B));
   do(n*B/(A+B));
}

void print(int n) {
   int i;
   for (i=0;i<ni++)
      printf("-");
}

He's what I got to so far:
function "do()" calls itself recursively until:
\frac{n\cdot{A}^k}{(A+B)^k}\leq1\\n\cdot\left(\frac{A}{A+B}\right)^k\leq1\\k\leq\log_{\frac{A}{A+B}}{\frac{1}{n}}
So far the time complexity is O(n\cdot\log{\frac{1}{n}}) (since each recursive call the do() function calls the print() function who's complexity is O(n)). But then the function starts calling itself from the second recursive call. I'm not sure how to continue from here.

Please help!

[dirk_gently]

I can see I made a mistake in the previous post, since each time I call the print function variable n changes...
Can someone please give me a direction here?
It's pretty urgent!

[darkagn]

The print function is O(n), so you were right the first time. Although n changes each call to print, it is still O(n) since each time print is called it takes roughly n steps to compute.

I'm not completely sure, but I think the second recursive call will also be O( n.log(1/n) ), since it basically does the same thing as the first recursive call. (That's assuming your logic was correct - I haven't checked it). So your overall algorithm is:
O( n.log(1/n) + n.log(1/n) )
= O( 2n.log(1/n) )

This is equivalent to O( n.log(1/n) ) since the constant '2' has little bearing over the time complexity as n -> infinity.

I hope that this helps, let me know if you need more explanation :)

[sarehu]

A/(A+B) is less than 1, so O(log base A/(A+B) of (1/n)) is not equivalent to O(log (1/n)). Rather, it's equivalent to O(- log (1/n)), since log(A/(A+B)) < 0. Then, since log (1/n) = - log (n), we have O(- log (1/n)) = O(log n). Then the whole thing would be O(n log n).

The reasoning here was kind of vague and lucky.

Let's define T to be the number of steps of our function. Then

T(n) = n + T(n*(A/(A+B))) + T(n*(B/(A+B))

Let u=A/(A+B), v=(B/(A+B)). Then

T(n) = n + T(un) + T(vn).

You could then use the Akra-Bazzi method to show it's O(n log n), noting that u+v=1. http://en.wikipedia.org/wiki/Akra-Bazzi_method

[dirk_gently]

A/(A+B) is less than 1, so O(log base A/(A+B) of (1/n)) is not equivalent to O(log (1/n)). Rather, it's equivalent to O(- log (1/n)), since log(A/(A+B)) < 0. Then, since log (1/n) = - log (n), we have O(- log (1/n)) = O(log n). Then the whole thing would be O(n log n).

The reasoning here was kind of vague and lucky.

Let's define T to be the number of steps of our function. Then

T(n) = n + T(n*(A/(A+B))) + T(n*(B/(A+B))

Let u=A/(A+B), v=(B/(A+B)). Then

T(n) = n + T(un) + T(vn).

You could then use the Akra-Bazzi method to show it's O(n log n), noting that u+v=1. http://en.wikipedia.org/wiki/Akra-Bazzi_method

Thanks a lot for the help!
That clarified things out for me. :)