mpsn Posted February 27, 2012 Share Posted February 27, 2012 Hi, for my assignment, I need to figure out how many possible paths through a bubblesort, Let n be the size of the array so my results are: if n = 0, 2^0 paths if n = 1, 2^1 paths if n = 2, 2^3 paths if n = 3, 2^6 paths if n = 4, 2^10 paths so I need to figure out a summation/product notation formula for the exponent, for a given size n so I mean 2^(some formula involving summation or multiplication notation) Any help appreciated Quote Link to comment Share on other sites More sharing options...
silkfire Posted February 27, 2012 Share Posted February 27, 2012 The formula for adding series starting from 1 to n is: n(n+1)/2. So for 4 it will be 4 * (4 + 1) / 2 = 20 / 2 = 10. Did that answer your question? Quote Link to comment Share on other sites More sharing options...
mpsn Posted February 27, 2012 Author Share Posted February 27, 2012 Thanks, appreciate it Quote Link to comment Share on other sites More sharing options...
mpsn Posted February 27, 2012 Author Share Posted February 27, 2012 Wait, actually I need to have a summation and/or product notation used, b/c yours is simply: 2^[n(n+1)/2], but I need 2^(summation from start to n for some formula) for instance. Quote Link to comment Share on other sites More sharing options...
Alex Posted March 2, 2012 Share Posted March 2, 2012 Wait, actually I need to have a summation and/or product notation used, b/c yours is simply: 2^[n(n+1)/2], but I need 2^(summation from start to n for some formula) for instance. The n(n+1)/2 is the value for the sum of numbers from 1 to n, so you're just looking for: Quote Link to comment Share on other sites More sharing options...
Recommended Posts
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.