answer is actually O(n^4)
nbd only close to failed the assignment on all the other time complexity questions
this is why i never just multiply loops with loops -_-;;
Computer Science Canada Big Oh quesiton |
| Author: | garywoot [ Thu Sep 26, 2013 1:41 am ] |
| Post subject: | Big Oh quesiton |
Hi guys, I have a quick question about the Big Oh for this algorithm: Algorithm alg x = 0 for i=0 to n^2 ......for j=0 to i ..........x = 3+i return x I only recently learned this so I'm not sure if what I'm doing is correct, but I arrived at the answer that the time complexity in Big Oh is O(n^3). Since outer loop excuses ~n^2 times, inner loop executes ~i times (minus constants), then inner loop total executes 1+2+3+...+n^2 times, therefore sum of k=1 to n of k^2 is n(n+1)(2n+1)/6 = O(n^3) could someone please tell me if what I'm doing is correct? Thanks a lot! |
|
| Author: | Insectoid [ Thu Sep 26, 2013 6:03 am ] |
| Post subject: | RE:Big Oh quesiton |
Yeah, you're correct. Complexity of nested loops is just the product of the complexity of each loop. n^2*n = O(N*3) |
|
| Author: | garywoot [ Fri Sep 27, 2013 7:39 pm ] |
| Post subject: | RE:Big Oh quesiton |
answer is actually O(n^4) nbd only close to failed the assignment on all the other time complexity questions this is why i never just multiply loops with loops -_-;; |
|
| Author: | Dreadnought [ Fri Sep 27, 2013 10:50 pm ] |
| Post subject: | Re: Big Oh quesiton |
garywoot wrote: Since outer loop excuses ~n^2 times, inner loop executes ~i times (minus constants), then inner loop total executes 1+2+3+...+n^2 times, therefore sum of k=1 to n of k^2 is n(n+1)(2n+1)/6 = O(n^3)
You had the right idea, I think you just got confused in your logic. You want the sum from k=1 to n^2 of k (which is O(n^4)), not the sum from k=1 to n of k^2 (which is O(n^3)). |
|
| Author: | garywoot [ Sat Sep 28, 2013 12:47 am ] |
| Post subject: | Re: Big Oh quesiton |
Dreadnought @ Fri Sep 27, 2013 10:50 pm wrote: garywoot wrote: Since outer loop excuses ~n^2 times, inner loop executes ~i times (minus constants), then inner loop total executes 1+2+3+...+n^2 times, therefore sum of k=1 to n of k^2 is n(n+1)(2n+1)/6 = O(n^3)
You had the right idea, I think you just got confused in your logic. You want the sum from k=1 to n^2 of k (which is O(n^4)), not the sum from k=1 to n of k^2 (which is O(n^3)). Ahh makes sense. |
|