2
$\begingroup$

I have the following equation: $$ h(n) = n \sum_{i=0}^{\lceil \log_2 n \rceil} \frac{m(2^i)}{2^i} $$

and I'm trying to understand exactly the relationship between the functions $h$ and $m$. The easiest way for me to do this is to fix $m$ to some specific function, then try to figure out what $h$ is. For example:

\begin{align} m(n) &= 1 &\Rightarrow h(n) &= n \\ m(n) &= \log n &\Rightarrow h(n) &= n\\ m(n) &= n &\Rightarrow h(n) &= n \log n \\ m(n) &= n^2 &\Rightarrow h(n) &= 2^n \end{align}

It would be really helpful, however, to be able to fix $h$ and find the cooresponding value of $m$. For example, what is $m$ if $h(n)=n^2$?

Is there some general procedure for doing this? Am I even approaching this problem in the right way?


Edit: In particular, I'd especially like to find out what $h$ and $m$ are equal to when $h(n) = m(n)$.

  • 1
    There's a variable $x$ on your left hand side that is nowhere on the right, so I don't follow you from line 1. Is that $x$ supposed to be $n$?2012-10-19
  • 0
    @alex.jordan You're right. Fixed.2012-10-19
  • 0
    This seems to me to be a problem that "$\textit{difference}$ equations" (not to be confused with $\textit{differential}$ equations) and the "difference calculus" can solve. You can look for the phrases in quotes to get more information. Essentially, You apply the difference delta to both sides (to get $\Delta h(n)=\Delta n f(m,n)$). Then solve the corresponding difference equation. I'll see if I can come up with a generalized procedure for doing this, or at least a specific example...2012-10-21

1 Answers 1