-1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Every function is it's own big theta. $\endgroup$ – Yuval Filmus Feb 3 '17 at 12:51
  • $\begingroup$ Is there a simplified form of the function like $ logn $ ? $\endgroup$ – LanceHAOH Feb 3 '17 at 12:52
  • $\begingroup$ 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! $\endgroup$ – Yuval Filmus Feb 3 '17 at 12:53
  • $\begingroup$ Is it possible to find the big theta without having to do trial and error? I intuitively guessed that the answer would be $ logn $ $\endgroup$ – LanceHAOH Feb 3 '17 at 12:54
  • $\begingroup$ Experience really helps. $\endgroup$ – Yuval Filmus Feb 3 '17 at 12:56
3
$\begingroup$

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)$.

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

$ 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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.