# Calculating time complexities

Page 1 of 1

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

### #1 AIintern

Reputation: 0
• 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

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

Reputation: 8370
• Posts: 31,956
• Joined: 06-March 08

## Re: Calculating time complexities

Posted 04 April 2013 - 07:18 PM

What are you talking about ?

### #3 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 11790
• Posts: 44,305
• 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.