0
$\begingroup$

I am an undergraduate student in Computer Engineering and going through one of the textbook examples, I am asked to prove that

$T(n)$ is $O(\log{}n)$

Where $T(n)= 5\log_{2} 2n +7$. I understand that this means that I must prove that $5\log_{2} 2n +7 \leq\lambda log(n)$

For some in n in a neighborhood of infinity. How exactly would I proceed with this?

$\endgroup$
4
  • 2
    $\begingroup$ Have you tried anything yourself? Why did your approaches fail? $\endgroup$ Oct 14, 2015 at 15:04
  • $\begingroup$ The thing is i dont understand how I am to begin $\endgroup$
    – pingOfDoom
    Oct 14, 2015 at 15:08
  • 1
    $\begingroup$ Looking into it, the professor and the book both describe ways of picking some arbitrary n>a and then building the inequality, eventually landing at some lambda value $\endgroup$
    – pingOfDoom
    Oct 14, 2015 at 15:17
  • $\begingroup$ possible duplicate: cs.stackexchange.com/q/824/755 $\endgroup$
    – D.W.
    Oct 14, 2015 at 18:38

1 Answer 1

1
$\begingroup$

$$5\log_2(2n)+7=5\log_2 n+5\log_2 2+7=5\log_2 n +12$$ Since for example $12\le 12\log_2 n$ for $n\ge 2$, it follows that $$5\log_2 n +12\le 5\log_2 n +12\log_2 n=17\log_2 n $$ for $n\ge 2$. This yields $O(\log n) $.

$\endgroup$
3
  • 2
    $\begingroup$ While this answers the question, it is common usage to not answer a question until the OP has made a serious effort at solving it on their own and (in the case of such a basic question) showed their attempts and why they failed. $\endgroup$ Oct 14, 2015 at 15:21
  • 1
    $\begingroup$ Sorry. I am sick and bored.. :) $\endgroup$
    – Danny
    Oct 14, 2015 at 15:23
  • $\begingroup$ @Danny Here, take these. $\endgroup$
    – Raphael
    Oct 15, 2015 at 10:18

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