0

I'm having hard times solving this problem

What value is returned by the following function? Express your answer as a function of n. Give the worst-case running time using Big Oh notation.

function pesky( n)  
r := 0  
for i := 1 to n do  
  for j := 1 to i do  
    for k := j to i + j do  
      r := r +1  
return(r)

First, I try to represent this function mathematically and simplify it

enter image description here

To check my solution I've created a method 

public static int mystery(int n) {
    int r = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            for (int k = j; k <= i + j; k++) {
                r++;
            }
        }
    }
    return r;
}

And it turns out that I did something wrong. Any help or hint highly appreciated.

4

1 回答 1

1

内部总和错误

\sum_{k=j}^{i+j} 1 = i+1
于 2013-04-28T15:24:41.600 回答