1

Without the ceilings, the solution is reasonable clear (given here).

Is there a way to reach a solution with the ceilings, or the difference between the two?

Community
  • 1
Complicated
  • 11
  • Are you only looking for the asymptotic (which is relatively easy) or are you looking for a closed form (which seems less likely)? – Milo Brandt Apr 05 '15 at 01:08
  • Any recurrence $T(n)=T(n-1)+f(n)$ has solution $T(n) = T(1)+\sum_{k=2}^n f(k)$. In your case, $\sum_{k=2}^n f(k)$ can be estimated using $\log k\le f(k)\le \log k+1$ –  Apr 05 '15 at 01:43
  • @Meelo I was looking for closed form. – Complicated Apr 05 '15 at 02:08

1 Answers1

0

I'll do this solution, although you may not like it, and it might not work. $$f(n+1)=f(n)+c \cdot \log(n)$$ We'll define c in a little bit. Also we'll start at $n=1$ and use the power and multiplication rules. $$f(2)=\log(1^c)+\log(2^c)=c \cdot \log(1\cdot2)$$ $$f(3)=c \cdot \log(1\cdot2)+c \cdot \log(3)=c \cdot \log(1\cdot2 \cdot 3)$$ Its fairly obvious this is just a factorial... $$f(n)=c \cdot \log(n!)$$ For generality, use the gamma function... $$f(n)=c \cdot \log(\Gamma(n+1))$$ with $c=1$, this is a famous result in and of its self. Here's the part that might upset you. c is actually the operator for the ceiling function! $$f(n)=ceiling(\log(\Gamma(n+1))$$

Zach466920
  • 8,341
  • In OPs case $c$ needed to be the ceil function, but as it is not linear, your reasoning doesn't apply. – Christoph Apr 07 '15 at 15:53
  • @Christoph fixed that. I guess that's true, but I really only answered because it looked like Op wasn't getting any feedback. My answer also shows the level of "creativity" that must be applied if you really want a solution. – Zach466920 Apr 07 '15 at 16:01