# Finding closed forms for the return values


int coffee(int n) {
int s = n * n;
for (int q = 0; q < n; q++)
s = s - q;
for (int q = n; q > 0; q--)
s = s - q;
return s + 2;
}

int tea(int n) {
int r = 0;
for (int i = 1; i < n*n*n; i = i * 2)
r++;
return r * r;
}

int mocha(int n) {
int r = 0;
for (int i=0; i<=n; i = i+16)
for (int j=0; j<i; j++)
r++;
return r;
}

int espresso(int n) {
int j=0;
for (int k = 16; coffee(k) * mocha(k) - k <= n; k+=16) {
j++;
cout << "I am having so much fun with asymptotics!" << endl;
}
}
return j;


I am trying to find the returning value in terms of $$n$$ for coffee, tea, mocha, but I am stuck right now.

I know coffee will return 2 as the code follows:

$$s = n^2$$

$$s = n^2 - \displaystyle\sum_{q=0}^{n-1}q = n^2 - \dfrac{n(n-1)}{2}$$

$$s = n^2 - \dfrac{n(n-1)}{2} - \displaystyle\sum_{q=1}^n q = n^2 - \dfrac{n(n-1)}{2} - \dfrac{n(n+1)}{2} = 0$$

Then, $$s = 0 + 2$$.

However, I can't seem to figure out tea, mocha, and espresso, because they don't follow +1 increments. Could anyone help me out how to compute the return value in terms of $$n$$?

For coffee, you can replace the less than with $$\leq n^3-1$$ and since you’re counting the number of doubling, the answer will be $$\lfloor(\log(n^3-1,2))+1\rfloor$$
For mocha firstly notice inner loop is equivalent to r+=i and the sum becomes $$16 \cdot \lfloor(n/16)\cdot(\lfloor(n/16)+1)/2 \rfloor \rfloor$$