2 Replies - 1799 Views - Last Post: 04 April 2013 - 10:49 PM

#1 AIintern  Icon User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 53
  • Joined: 06-June 12

Calculating time complexities

Posted 03 April 2013 - 08:11 AM

I hope this is in the right place. If not I am sorry.

We are going over time complexities in class and I am confused about a few things.


I understand the base case, but when it comes to T(n)= I get lost.

I guess ill post an example to take you through how I think, and hopefully you guys can break down where I am wrong/correct.


tri2(int size, int n)
{
   if(n>0)
   { 
     tri2(size, n-1)
     for (int i = 0; i < size-n; i++)
           print(" ");
     for (int i=1; i <=2*n-1; i++)
           println(n);
     println();
   }            
}



Thats just a summary of the code (not exact)

But here I go

If N>0 it will go into the loop, so the base case will be
T(0)=1

now on to T(N)
I see one recursive call so i will add T(n-1) to my equation
T(n)=T(n-1)

I see 2 loops repeating n times. So I will add 2n

T(n)=T(n-1)+2n

I simplify that and end up with

T(n)=T(n-1)+n


I guess where I am confused is I'm not sure when to add 1, or add n or add 2n.. Im just really confused.. any help would be awesome. Thanks guys.

Is This A Good Question/Topic? 0
  • +

Replies To: Calculating time complexities

#2 pbl  Icon User is offline

  • There is nothing you can't do with a JTable
  • member icon

Reputation: 8315
  • View blog
  • Posts: 31,836
  • Joined: 06-March 08

Re: Calculating time complexities

Posted 04 April 2013 - 07:18 PM

What are you talking about ?
Was This Post Helpful? 0
  • +
  • -

#3 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10180
  • View blog
  • Posts: 37,585
  • Joined: 27-December 08

Re: Calculating time complexities

Posted 04 April 2013 - 10:49 PM

Moved to Computer Science.

Working backwards is a good strategy when analyzing recursive algorithms. So:
T(n) = T(n-1) + size-n + 2n-1 = T(n-1) + size + n - 1
T(n-1) = T(n-2) + size-n-1 + 2(n-1) - 1 = T(n-2) + size + n - 4
T(n-2) = T(n-3) + size-n-2 + 2n-5 = T(n-3) + size + n - 7

Do you see the pattern? This should get you going in the right direction.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1