# Time Complexity Help

Page 1 of 1

## 7 Replies - 911 Views - Last Post: 05 March 2011 - 10:05 PM

### #1 Matty919

Reputation: 1
• Posts: 83
• Joined: 10-May 09

# Time Complexity Help

Posted 03 March 2011 - 02:39 PM

What would the time complexity of the following be:

```For blah
statements
End For

For blah
For blah
statements
End For
End For

```

I think the first for loop will have time complexity O(n) and the second O(n^2) but what would the combined time complexity of the algorithm be?
Is This A Good Question/Topic? 0

## Replies To: Time Complexity Help

### #2 BetaWar

• #include "soul.h"

Reputation: 1254
• Posts: 7,476
• Joined: 07-September 06

## Re: Time Complexity Help

Posted 03 March 2011 - 02:42 PM

You are correct, the first look is O(n) and the second is O(n^2), the combined complexity would be O(n+n^2), but considering big O likes to simplify arlgorithms that could go to simply O(n^2) because n^2 is the dominant term.

### #3 mostyfriedman

• The Algorithmi

Reputation: 727
• Posts: 4,473
• Joined: 24-October 08

## Re: Time Complexity Help

Posted 03 March 2011 - 03:20 PM

it also depends on the statements that are executed in the loops.

### #4 r.stiltskin

• D.I.C Lover

Reputation: 1833
• Posts: 4,927
• Joined: 27-December 05

## Re: Time Complexity Help

Posted 03 March 2011 - 04:49 PM

It also depends on the blah.

Consider
for(int i = 1; i < n; i *= 2 )

### #5 Nikitin

• D.I.C Regular

Reputation: 56
• Posts: 264
• Joined: 02-August 10

## Re: Time Complexity Help

Posted 03 March 2011 - 05:42 PM

Impossible to tell complexity from the provided information. Need to know how many times the loops will be executed, and the complexity of the statements.

### #6 Matty919

Reputation: 1
• Posts: 83
• Joined: 10-May 09

## Re: Time Complexity Help

Posted 05 March 2011 - 06:13 PM

For n = 0 to lengthof(A)
statements
End for

For n = 0 to lengthof(A)
For n = 0 to lengthof(A)
statements;
End For
End For

Does it depend on the statements?

### #7 Nikitin

• D.I.C Regular

Reputation: 56
• Posts: 264
• Joined: 02-August 10

## Re: Time Complexity Help

Posted 05 March 2011 - 09:38 PM

Yes

### #8 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 11072
• Posts: 41,539
• Joined: 27-December 08

## Re: Time Complexity Help

Posted 05 March 2011 - 10:05 PM

If it takes constant time for the statements inside the loops to run, then the time complexity is O(n^2). However, if the statements take more than constant time, then the complexity is O(kn^2), where k represents the time complexity of the statements. If k is a constant, it just gets dropped.