Big theta of $\lceil{log(n+1)}\rceil$

I am trying to calculate the big theta of $\lceil{log(n+1)}\rceil$.

I derived the following inequality:

$log(n+1) \le \lceil{log(n+1)}\rceil \le log(n+1) + 1$

Based on the definition of big theta, a function $f(n) \in \Theta({g(n))}$ iff $\exists \ c_1,\ c_2 > 0$ and a constant $k$ such that $\forall n \ge k$, $c_1\cdot g(n)\le f(n) \le c_2 \cdot g(n)$

This means that we must define the inequality in terms of multiplicative constants. However, I have no idea how to formulate such an equation. Could someone please advise me?

• Every function is it's own big theta. – Yuval Filmus Feb 3 '17 at 12:51
• Is there a simplified form of the function like $logn$ ? – LanceHAOH Feb 3 '17 at 12:52
• Yes, the two functions are big thetas of one another. It's a nice exercise to show it directly using the definition of big theta. Good luck! – Yuval Filmus Feb 3 '17 at 12:53
• Is it possible to find the big theta without having to do trial and error? I intuitively guessed that the answer would be $logn$ – LanceHAOH Feb 3 '17 at 12:54
• Experience really helps. – Yuval Filmus Feb 3 '17 at 12:56

There is no such thing as "the big-theta of a function", just as there is no such thing as "the number that's approximately equal to $\pi$." There are infinitely many functions $f$ such that $\log(n+1)=\Theta(f)$.

• Ah! That's right. How do I obtain the most simplified $\Theta(f)$? – LanceHAOH Feb 3 '17 at 13:39
• @LanceHAOH Define "most simplified". – Raphael Mar 5 '17 at 16:50

$log(n+1) \le \lceil{log(n+1)}\rceil \le log(n+1) + 1$

Based on the definition of big theta, a function $f(n) \in \Theta({g(n))} >$ iff $\exists \ c_1,\ c_2 > 0$ and a constant $k$ such that $\forall >n \ge k$, $c_1\cdot g(n)\le f(n) \le c_2 \cdot g(n)$

This means that we must define the inequality in terms of multiplicative >constants.

Remark that

$log_b n<log_b(n+1) \le \lceil{log_b(n+1)}\rceil \le log_b(n+1) + 1< 3\log_b n$

for $n>1$.