0
$\begingroup$

Given the following code:

void aux(int n){
   while (n > 0) {
   printf("%d", n);
   n--;
  }
}
long f1(int n)
{
  long sum = 0;
  for (int i = 1; i * i <= n; i++) {
    for (int j = 1; j <= i; j++) {
      aux(i * j);
      sum += i * j;
     }
  }
 return sum;
}

I have calculated the time complexity of aux and I found it is $\Theta(n)$. Then I tried to find the time complexity of f1 and got the following expression:

$$ \sum_{j=1}^1 j + 2\sum_{j=1}^2j + 3\sum_{j=1}^3 j +...+ \sqrt{n} \sum_{j=1}^{\sqrt{n}} j $$

The right answer here is $\Theta(n^2)$ but I'm really not sure why that is the case. Can anyone explain if the expression I've got is correct, and if so why it is equal to the time complexity above?

$\endgroup$

1 Answer 1

1
$\begingroup$

Let $n=m^2$.

$$ \sum_{j=1}^1 j + 2\sum_{j=1}^2j + 3\sum_{j=1}^3 j +...+ m \sum_{j=1}^{m} j \\=1 + 2\cdot3 + 3\cdot6 +...+ m \frac{m(m+1)}2\\\sim\frac{m^4}8=\Theta(m^4)=\Theta(n^2) $$

by Faulhaber.


More precisely,

$$\frac{3m^4+10m^3+9m^2+2m}{24}=\frac{m(3m+1)(m+1)(m+2)}{24}.$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.