RSS

help computing time complexity

Please support our Computer Science advertiser: Programming Forums

Views: 884 | Replies: 4 | Thread Tools Display Modes

•

Join Date: Jan 2008

Posts: 4

Reputation: dirk_gently is an unknown quantity at this point

Rep Power: 0

Solved Threads: 0

dirk_gently dirk_gently is offline

Offline

Newbie Poster

help computing time complexity

Jan 26th, 2008

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

 Help with Code Tags 
 c Syntax (Toggle Plain Text) 
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("-");
}
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!

•

Join Date: Jan 2008

Posts: 4

Reputation: dirk_gently is an unknown quantity at this point

Rep Power: 0

Solved Threads: 0

dirk_gently dirk_gently is offline

Offline

Newbie Poster

Re: help computing time complexity

Jan 27th, 2008

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!

•

Join Date: Aug 2007

Location: Adelaide, South Australia

Posts: 451

Reputation: darkagn will become famous soon enough

Rep Power: 3

Solved Threads: 57

darkagn

Offline

Posting Pro in Training

Re: help computing time complexity

Jan 27th, 2008

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

The answer is 42.

•

Join Date: Oct 2007

Location: Cambridge, MA

Posts: 269

Reputation: sarehu is on a distinguished road

Rep Power: 2

Solved Threads: 22

sarehu

Offline

Posting Whiz in Training

Re: help computing time complexity

Feb 1st, 2008

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

•

Join Date: Jan 2008

Posts: 4

Reputation: dirk_gently is an unknown quantity at this point

Rep Power: 0

Solved Threads: 0

dirk_gently dirk_gently is offline

Offline

Newbie Poster

Re: help computing time complexity

Feb 3rd, 2008

•

Originally Posted by 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

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