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

#1 Matty919  Icon User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • 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  Icon User is offline

  • #include "soul.h"
  • member icon

Reputation: 1148
  • View blog
  • Posts: 7,148
  • 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.
Was This Post Helpful? 2
  • +
  • -

#3 mostyfriedman  Icon User is offline

  • The Algorithmi
  • member icon

Reputation: 727
  • View blog
  • 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.
Was This Post Helpful? 0
  • +
  • -

#4 r.stiltskin  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1833
  • View blog
  • 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 )
Was This Post Helpful? 0
  • +
  • -

#5 Nikitin  Icon User is offline

  • D.I.C Regular

Reputation: 56
  • View blog
  • 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.
Was This Post Helpful? 0
  • +
  • -

#6 Matty919  Icon User is offline

  • D.I.C Head

Reputation: 1
  • View blog
  • 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?
Was This Post Helpful? 0
  • +
  • -

#7 Nikitin  Icon User is offline

  • D.I.C Regular

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

Re: Time Complexity Help

Posted 05 March 2011 - 09:38 PM

Yes
Was This Post Helpful? 0
  • +
  • -

#8 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10563
  • View blog
  • Posts: 39,087
  • 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.
Was This Post Helpful? 1
  • +
  • -

Page 1 of 1