Thread: big-Oh

I just need some help finding the run time of my program in the general big-Oh notation. what my program does is takes a 2d array of numbers adds all the possibilities to make 1d sets and then finds the highest sum of the of all the possible sets.
ex
given:

Code:

0    -2    -7    0

9     2    -6    2

-4    1    -4    1

-1    8     0    -2

the program makes

Code:

0   -2   -7     0     //first row
9    0   -13    2     //first and second
5    1   -17    3     //row 1-3
4    9   -17    1     //row 1-4
9    2   -6     2     //row 2
5    3   -10    3     //row 2-3
4    11  -10    1     //row 2-4
-4   1   -4     1     //row 3
-5   9   -4    -1     //row 3-4
-1   8    0    -2     //row 4

and the highers set sum of each line is

Code:

0
9
6      //5+1
13     //4+9
11     //9+2
8      //5+3
15     //4+11
1
9
8

then it displays the highest sum.

what i got is O(n^3) (assuming m is about equal to n)
and this is how...

n = hight
m = length

for the first part...

Code:

            S =   n  + n-1 + ... +  2  +  1
+           S =   1  +  2  + ... + n-1 +  n
--------------------------------------------
           2S =  n+1 + n+1 + ... + n+1 + n+1
           2S =  n(n+1)
            S = (n^2+n)/2

that is for the number of new sets made

and then add m, S times so... (m is about equal to n so i replace m with n)

Code:

m*S 
= m * (n^2+n)/2
= n(n^2+n)/2
= (n^3+n^2)/2

this give O(n^3)

I'm not sure that I am using the length part right.

I need to know because my program is also graded on efficiency, this is the first class that has done this, and i want to make sure i get the most points possible. I'm worried that I'm wrong because I came up with this solution in about an hour and according to my assignment O(n^3) is the best possible solution. So I want to make sure I didn't over look anything.

There are Θ(n^2) new sets, that is true. What matters for efficiency is what you actually do to process those sets. If you isolate just one of your new sets, how much work does it take your code to find the highest partial sum in that set? That's the multiplier you need to multiply n^2 by.

i know it will take "m" to find the highest sum in each of the new sets. so i guess i was right, O(n^3), b/c n^2*m = n^3 (m is about the same as n). thanks for confirming.