Home /
Expert Answers /
Computer Science /
answer-each-of-the-following-questions-justify-your-answers-using-either-the-definitions-of-o-pa347
(Solved): Answer each of the following questions. Justify your answers using either the definitions of O,, ...
Answer each of the following questions. Justify your answers using either the definitions of , and or the techniques shown in class (along with basic math). Note: for limit tests involving logs, you may ignore any constants generated by taking derivatives of the log; that is, you may assume its base is . This assumption is permissible because any log can be converted to a natural by multiplying by a constant, which does not affect the outcome of the test. 4. Does ? 5. Does ? 6. Does ? 7. Does ? 8. Does ? 9. Let and be non-negative functions of . Prove using the definitions of , and - not using limit tests - that if , then . 10. Let and be non-negative functions of . If , does ? Justify your answer.
Expert Answer
4. To determine whether , we must analyze the growth rate of the two terms.Using basic algebra, we can expand . Since the highest order term is , we can ignore the lower order term in our comparison with .We can use the definition to determine the growth rate of nlogn. We want to find the sequence c1, c2 and such that for all Taking the lower limit, .Dividing both sides by gives . The right side of the inequality, , approaches n as n approaches infinity, while the left side grows logarithmically. Therefore, it is impossible to find a sequence of c1, c2, and n0 to satisfy the definition of .