Computer Science Canada Programming C, C++, Java, PHP, Ruby, Turing, VB   Username:   Password: Wiki   Blog   Search   Turing   Chat Room  Members
Big Oh quesiton
Author Message
garywoot

Posted: 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!

Insectoid

Posted: 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

Posted: Fri Sep 27, 2013 7:39 pm   Post subject: RE:Big Oh quesiton

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: 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

Posted: 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: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First

Page 1 of 1  [ 5 Posts ]
 Jump to:  Select a forum  CompSci.ca ------------ - Network News - General Discussion     General Forums   -----------------   - Hello World   - Featured Poll   - Contests     Contest Forums   -----------------   - DWITE   - [FP] Contest 2006/2008   - [FP] 2005/2006 Archive   - [FP] 2004/2005 Archive   - Off Topic     Lounges   ---------   - User Lounge   - VIP Lounge     Programming -------------- - General Programming     General Programming Forums   --------------------------------   - Functional Programming   - Logical Programming   - C     C   --   - C Help   - C Tutorials   - C Submissions   - C++     C++   ----   - C++ Help   - C++ Tutorials   - C++ Submissions   - Java     Java   -----   - Java Help   - Java Tutorials   - Java Submissions   - Ruby     Ruby   -----   - Ruby Help   - Ruby Tutorials   - Ruby Submissions   - Turing     Turing   --------   - Turing Help   - Turing Tutorials   - Turing Submissions   - PHP     PHP   ----   - PHP Help   - PHP Tutorials   - PHP Submissions   - Python     Python   --------   - Python Help   - Python Tutorials   - Python Submissions   - Visual Basic and Other Basics     VB   ---   - Visual Basic Help   - Visual Basic Tutorials   - Visual Basic Submissions     Education ----------- - Student Life   Graphics and Design ----------------------- - Web Design     Web Design Forums   ---------------------   - (X)HTML Help   - (X)HTML Tutorials   - Flash MX Help   - Flash MX Tutorials   - Graphics     Graphics Forums   ------------------   - Photoshop Tutorials   - The Showroom   - 2D Graphics   - 3D Graphics     Teams ------ - dTeam Public

 Style: Appalachia blueSilver eMJay subAppalachia subBlue subCanvas subEmjay subGrey subSilver subVereor Search: