-1
$\begingroup$

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$?

$\endgroup$
0
$\begingroup$

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$$

I’m pretty sure you can work out the last function. Sorry if this is unclear. I’ll edit this better when I get my laptop

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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