Programming C, C++, Java, PHP, Ruby, Turing, VB
Computer Science Canada 
Programming C, C++, Java, PHP, Ruby, Turing, VB  

Username:   Password: 
 RegisterRegister   
 Big Oh quesiton
Index -> General Programming
View previous topic Printable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic
Author Message
garywoot




PostPosted: 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!
Sponsor
Sponsor
Sponsor
sponsor
Insectoid




PostPosted: 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)
garywoot




PostPosted: 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 -_-;;

Posted Image, might have been reduced in size. Click Image to view fullscreen.
Dreadnought




PostPosted: 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)).
garywoot




PostPosted: 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.
Display posts from previous:   
   Index -> General Programming
View previous topic Tell A FriendPrintable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic

Page 1 of 1  [ 5 Posts ]
Jump to:   


Style:  
Search: