3

I am working on some homework so I cannot post any code. I am working on some code and at this point I have something like this (instead of functions I wrote time complexity):

while(O(n^2)) {
    O(n^4);
    O(n^2);
}

I estimated O's according to nested for-loops I have in functions. My question is what is actually time complexity of this whole thing? I wouldn't mind short explaination either. Thank you!

CAPS LOCK
  • 1,960
  • 3
  • 26
  • 41
  • Could you please clarify one thing? By `while(O(n^2))` you mean that "the loop iterates n^2 times" or "calculating whether we want to end the loop takes O(n^2)" and in no way indicates number of iterations? – Darth Hunterix Nov 06 '13 at 20:31
  • Parameter in while is function call. It's the same like: `function() { O(n^2); }` and `while(function()) { O(n^4); O(n^2); }` – CAPS LOCK Nov 06 '13 at 20:37
  • Ok, I will update my answer then. – Darth Hunterix Nov 06 '13 at 20:38

2 Answers2

2

EDIT: My previous answer was wrong, because I have made a mistake.

Now I understand, that your code can be refactored to

while(run == true)
{
    run = O(n^2);
    O(n^4);
    O(n^2);
}

so each iteration has O(n^4) complexity, because we have a polynomial n^4 + 2*(n^2) and we ditch the lower degree. Now you have to multiply it by number of iteration. For example if you get n iteration you end up with O(n^5). If you always have 1000000000 iterations, you still have O(n^4).

An excellent explanation of Big-O notation is here: What is a plain English explanation of "Big O" notation?

Community
  • 1
  • 1
Darth Hunterix
  • 1,484
  • 5
  • 27
  • 31
  • So while(O(n^2)) is equivalent to two extra nested for-loops? Then I agree this will be O(n^6). – CAPS LOCK Nov 06 '13 at 20:08
  • I answered that, but I deleted my comment because I spotted a flaw in my logic. Wait before accepting any answer, ok? I have to think about it. – Darth Hunterix Nov 06 '13 at 20:27
  • Yes. It's a bit tricky. while itself should be O(n). But this one has O(n^2) in it. That's what's bothering me the most. – CAPS LOCK Nov 06 '13 at 20:29
  • Well it depends on your answer to my comment under the question :) If it's just n^2 iterations, then O(n^6) is your answer. If not, then all we know is that each iteration takes O(n^4), but we know nothing about the algorithm itself. – Darth Hunterix Nov 06 '13 at 20:34
1

What are you specifically trying to find out? If you want to know how long your code takes to compute, and break this down into specific loops and nested loops then I'd suggest looking into the stopwatch class:

http://msdn.microsoft.com/en-us/library/system.diagnostics.stopwatch(v=vs.110).aspx

Also you can watch the times live using by writing the elapse time of the stopwatches to labels and then calling me.update()

FraserOfSmeg
  • 1,128
  • 2
  • 23
  • 41
  • In this question I am not asking about time in seconds, milliseconds, etc. I have stopwatches implemented, though. I am asking about big-O algorithm time complexity of that whole while-loop. – CAPS LOCK Nov 06 '13 at 19:45
  • Ah I see, sorry. Based on the complexities you've stated I'd guess it was O(n^8). I'm thinking this because the two terms inside the while-loop would add time together (and the lower term can be omitted leaving you with O(n^4)) but the loop would then require this to be run O(n^2) time and hence this would multiply O((O(n^4))^2) = O(n^8). I hope that's helpful. – FraserOfSmeg Nov 06 '13 at 19:53
  • No problem. That's better. But now I have two answers. One saying O(n^6), and your with O(n^8). It will sure be better for my grade that's O(n^6), heh. However, it will be nice to improve the code as current complexity is just way too high. – CAPS LOCK Nov 06 '13 at 20:03
  • Any chance you could share the loops and some info about what goes on inside the loops. It'd be much easier to suggest reorganisation if you do so. Also I'm no expert when it comes to time complexity so I wouldn't necessarly trust my answer over Darth Hunterix's. – FraserOfSmeg Nov 06 '13 at 20:08
  • Those are just nested loops where the last one is doing more expensive calculations (multiplication). I've done some research and everything looks that O(n^6) is the right answer. Thank you anyway for response. – CAPS LOCK Nov 06 '13 at 20:14
  • 1
    Like I stated in my answer: We repeat n^4 operation n^2 times (and we ditch n^2), so it's (n^2)*(n^4) = n^(2+4) = n^6. To make it n^8 it would have to be (n^4)^2. – Darth Hunterix Nov 06 '13 at 20:22