Recursive Algorithm Complexity?

Question

I had the following question before:

Given a recursive algorithm T(n), Find a function f(n) for which .

Note: k is constant and > 3, and for n<=1, T(n)=0.

How can I solve such question?

Answer 1

Well, I won't show all my steps. This is your homework problem, but here's an overview:

• Based on the recursion definition, we can break down the summation:

  T(n) = 
      n 
    + T(floor(n / k)) 
    + T(floor(n / k ^ 2)) 
    + ... 
    + T(floor(n / (k ^ log(n))))
  

• Then from this, we can get an iterative definition:

    T(n) = 
        n 
        + floor(n / k) 
        + 2 * floor(n / k ^ 2) 
        + ... 
        + 2 ^ (log(n) - 1) 
            * floor(n / k ^ (log(n)))
  

  or

  T(n) = 
    n 
    + Sum(
        floor(n / k ^ i) * 2 ^ (i), 
        i=1, log(n)
    ) / 2
  

Your question asks for big Theta. This means we need to figure out an upper and lower bound.

• Upper bound: floor(x) <= x, so we drop the floor and simplify:

  O(
      n + n / (k - 2)                       <-- O(n)
      + (n * (2 / k) ** log(n)) / (k - 2)
  )
  

  Because k > 3 > 2, the final term is guaranteed to grow less than n, so we're left with O(n).

• Lower bound: The Sum(...) > 0 always, so we can bound it below with just n, giving Omega(n).

Because T is both O(f(n)) and Omega(f(n)) for f(n) = n, we can say that it is also Theta(n), so an answer would be

f(n) = n

---

Here's a program that demos an upper and lower bound. This program is not the equivalent of a proof, but it can help you see what's going on. I grew n exponentially, so if you plot the values on a log scale, it should show the lines and the asymptotic behavior.

const k = 4;
const logK = Math.log(k);

function T(n) {
  if (n <= 1)
   return 0;
  
  let acc = n;
  for (let i = 1; i <= Math.log(n) / logK; i++)
    acc += T(Math.floor(n * k ** -i));
  
  return acc;
}

function nonRecT(n) {
  let acc = n;
  for (let i = 1; i <= Math.log(n) / logK; i++) {
    let f = Math.floor(n * k ** -i);
    acc += f > 1 ? f * 2 ** (i - 1) : 0;
  }
  return acc;
}

for (let n = k; n <= k ** 20; n *= k) {
  console.log([
    n,
    T(n), nonRecT(n),
    n * (1.5 + 1 / (k - 2))
  ].join('\t'));
}