Timeline for Big-O of this algorithm?
Current License: CC BY-SA 3.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 23, 2017 at 12:40 | history | edited | CommunityBot |
replaced http://stackoverflow.com/ with https://stackoverflow.com/
|
|
| Aug 2, 2013 at 20:18 | history | migrated | from stackoverflow.com (revisions) | ||
| Jul 27, 2013 at 5:46 | vote | accept | CommunityBot | ||
| Jul 26, 2013 at 21:04 | comment | added | Jens Gustedt |
I have the impression that you are trying to prove a lower bound. Big-O is looking for an upper bound. Stating that the algorithm is O(n^3) is trivial. Omega(n^3) is the difficult part.
|
|
| Jul 26, 2013 at 20:07 | comment | added | ChrisCM | But I believe you're correct, the tightest bound is n^3/4, which is O(n^3) | |
| Jul 26, 2013 at 20:00 | comment | added | ChrisCM | Well, yes, but under this logic O(N^2) is also O(N!). Why not just leave it at that? On possible motivation in O-notation is to find the tightest bounding function. There is a significantly tighter bounding function in this case than n^3. Sometimes we want this tighter bound, sometimes we don't care. But saying cut and dry, it's n^3 is incorrect. If you're solving a problem like this you should at least be aware of this nuance, before ignoring it. | |
| Jul 26, 2013 at 19:56 | comment | added | Mehdi Karamosly | stackoverflow.com/questions/766939/… | |
| Jul 26, 2013 at 19:55 | comment | added | Fallen |
actually you're right, it might be less than n^3, but big O is not calculated that way :) for an example for(i=0;i<n;i++)for(j=i+1;j<n;j++) needs actually (N*(N-1))/2 operations but still it's an O(N^2) algorithm
|
|
| Jul 26, 2013 at 19:53 | comment | added | Mehdi Karamosly |
@Fallen it is n x n/2 x n/2 I think but still considered as O(n^3)
|
|
| Jul 26, 2013 at 19:51 | comment | added | ChrisCM | @Fallen: I'm not sure, but it is considerably less than for(i < n)for(j<n)for(k<n), which is n^3. | |
| Jul 26, 2013 at 19:47 | comment | added | Fallen |
@ChrisCM: for(int i=0;i<n;i++)for(int j=i+1;j<n;j++)for(int k=0;k<i;k++) what should be the complexity for these three loops? ;-)
|
|
| Jul 26, 2013 at 19:44 | comment | added | ChrisCM | I don't believe that it is in fact O(n^3), this line of logic is ignoring the (c=i+1) line, which is very much diminishing the amount of work the inner loops need to do. I am working on an answer. I believe the tightest bounding function is actually O(n^2) | |
| Jul 26, 2013 at 19:43 | comment | added | positiveimpact | So the inner-most loop is O(n). But, why does this mean that the whole algo. is O(n^3)? I made a good guess, but I'm still not sure why. I see your statement that it's O(n^3), but why is it n^k? | |
| Jul 26, 2013 at 19:37 | history | answered | Mehdi Karamosly | CC BY-SA 3.0 |