make 2 loops that are nested. one of those goes through the rows and one goes through columns. sum up all cells like this, so you'll finally get the sum of all cells.
its O(n^2) which is really crappy, but since nobody told you to find the best algorithm, this is the simplest.

now think about a formula how you can calculate the sum easier. how many "loops" you need?

Adding up each cell would give you an O(n^2) runtime.

If you look closely, each row is an arithmetic sequence, and there is a formula for calculating an arithmetic sequence. This means you can acheive an O(n) runtime by simply utilizing this.

why waste processing time when you can simplify it by a little thinking?

http://forums.d2jsp.org/topic.php?t=70122182&f=257

for this problem f(n)=n^3

lol yep, worked even for n=1

Well, thats what I get for not taking the next step.

Each row is an arithmetic sequence. There is a formula for calculating the sum of an arithmetic sequence



Which means an O(N) algorithm would be



But you can go a little further than that. Because the sum of every arithmetic sequence IS an arithmetic sequence. Every row you are adding N to the previous row's sum.

F(N) = (N/2) (2A + (N - 1)D)

D = N, A = G(N)

F(N) = (N/2) (2G(N) + (N - 1) N)
= (N/2) (2G(N) + N^2 - N)


G(N) = (N/2) (2A + (N - 1)D)

D = 1, A = 1

G(N) = (N/2) (2(1) + (N - 1) (1))
= (N/2) (2 + N - 1)
= (N/2) (N + 1)
= (N^2 + N) / 2

Subsitituting

F(N) = (N/2) ( 2 ( ( N^2 + N )/2) + N^2 - N)
= (N/2) (N^2 + N + N^2 - N)
= (N/2) (2N^2)
= 2N^3 / 2
= N^3

F(N) = N^3

So, time complexity for this function would be constant at O(1).


Interesting math problem. Boring algorithm. For a Data Structure and Algorithm course, the cool part is developing an algorithm to solving the problem. When the problem can be reduced to constant time, yea the math may be interesting, but it loses its luster. This is almost like a trick question from the professor.

This post was edited by Minkomonster on Feb 7 2014 12:18am

congratulation on your valiant effort to re-invent the wheel
seems you found my solution in the linked thread too simple

not really an interesting math problem once you look closely at the structure of the matrix
but yes, it might be intended as a trick question to teach the student to analyse a problem properly rather than to jump in and start coding based on the first impression
i did that once with my first program, but never again

Actually, from a teaching stand point I found your solution ridiculous. You don't explain why it works that way, or what you are using to get to your answer. Mine is simpler, and easier to follow.

Congratulations on your valiant effort to assert your alpha-status as math master. But if you want to continue to fire shots like a fucking cock sucker, then I will gladly allow this conversation to divert into a flame war.

you are just bullshitting and couldn't admit that someone did provide a solution while you were stuck
you don't understand how mirroring across the value n diagonal works?
why make it simple if you can complicate it

I explained it in terms of arithmetic series. And I specifically spoke to that. This is the first time you have given a name to the concept you deployed to solve the problem and you have still neglected to explain why it works. Further more, the math in your thread is jumbled and convoluted. To the outside reader it is indecipherable. Your solution is not simple for these reasons.



As an aside, I talked to OP in private messages and he validated my assertion by saying you left him more confused than when he asked the question. You didn't help shit. He wasn't even asking for a solution, he was asking for guidance on how to go about solving it. You failed to provide that. You failed.

that must be the reason he posted



and exchanged a few pms with me



This post was edited by brmv on Feb 7 2014 09:04am