Time Complexity Help

Page 1 of 1

7 Replies - 747 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: 1107
• Posts: 6,924
• 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: 726
• 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

• Self-Trained Economist

Reputation: 10196
• Posts: 37,655
• 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.