How can I write a recursive function having $\Theta(n^7)$?

Question

How can I write a recursive function having $\Theta(n^7)$ cost? I must only use if, then, else statements and a function called $G(n)$ that costs $\Theta(n)$.

For example:

funz(n) {
if(n <= 1) 
  return 0;
else {
  G(n);
  return funz(n-1);
}

This has a cost of $\Theta(n^2)$. I must write something similar but having $\Theta(n^7)$ cost.

Obviously I can't modify G(n) function.

Answer 1

The following algorithm has a Big-O complexity of $O(n^7)$:

fn(n) {
    if (n < 0)
        return 0;
    else {
        G(n*n*n*n*n*n);
        return fn(n-1);
    }
}

The number of steps of this algorithm will be: $$ \sum_{i=1}^n i^6 = \cfrac{1}{42} n (n + 1) (2 n + 1) (3 n^4 + 6 n^3 - 3 n + 1) = \cfrac{1}{42} (6n^7 + 21n^6 + 21n^5 - 7n^3 + n) $$ So its Big-O complexity is $O(n^7)$.