Homework Help is Here – Start Your Trial Now!
Engineering
Computer Science
Yihan recently learned the asymptotical analysis. The key idea is to evaluate the growth of a function. For example, she now knows that n² grows faster than n. She wants to know whether she really understands the idea, so she has created a little task. First of all, she found a lot of functions here: log n² log(n!) 2+1 91 3n 92: n! 93 n²+ n 94 n³ 95 log² n 96 97 (2) 916 n 911 √n 912 log log n 98 913 (n+1)! 99 ln ln n 914 √log n 910 10000 915 log √n 920 n/logn Note: log n = log2 n; In n = loge n; log² n = (log n)2; n! is the factorial of n, i.e., n! = 1 x 2 x... x n. Reading the long list, Yihan realized that things were not as simple as she thought. Could you help her with the following problems? For all the questions in this problem, you only need to show your answer without explaining. The only exception is question (4), where you need to show proofs or explanations. (1) 917 2" 918 nlog n 919 5n²13n+6 What does polylogarithmic mean (use O(.), (.), w(), (), o(.) to present your answer)? Which of them are polylogarithmic? What does sublinear mean (use O(.), (.), w.), (.), o(.) to present your answer)? of them are sublinear? (3) What does superlinear mean (use O(.), (.), w), (), o(.) to present your answer)? Which of them are superlinear? Which

Yihan recently learned the asymptotical analysis. The key idea is to evaluate the growth of a function. For example, she now knows that n² grows faster than n. She wants to know whether she really understands the idea, so she has created a little task. First of all, she found a lot of functions here: log n² log(n!) 2+1 91 3n 92: n! 93 n²+ n 94 n³ 95 log² n 96 97 (2) 916 n 911 √n 912 log log n 98 913 (n+1)! 99 ln ln n 914 √log n 910 10000 915 log √n 920 n/logn Note: log n = log2 n; In n = loge n; log² n = (log n)2; n! is the factorial of n, i.e., n! = 1 x 2 x... x n. Reading the long list, Yihan realized that things were not as simple as she thought. Could you help her with the following problems? For all the questions in this problem, you only need to show your answer without explaining. The only exception is question (4), where you need to show proofs or explanations. (1) 917 2" 918 nlog n 919 5n²13n+6 What does polylogarithmic mean (use O(.), (.), w(), (), o(.) to present your answer)? Which of them are polylogarithmic? What does sublinear mean (use O(.), (.), w.), (.), o(.) to present your answer)? of them are sublinear? (3) What does superlinear mean (use O(.), (.), w), (), o(.) to present your answer)? Which of them are superlinear? Which

Database System Concepts
Database System Concepts
7th Edition
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Chapter1: Introduction
Section: Chapter Questions
Problem 1PE
See similar textbooks
icon
Related questions
Question
100%
Yihan recently learned the asymptotical analysis. The key idea is to evaluate the growth of a function. For example, she now knows that \( n^2 \) grows faster than \( n \). She wants to know whether she really understands the idea, so she has created a little task. First of all, she found a lot of functions here: - \( g_1 : 3^n \) - \( g_2 : n! \) - \( g_3 : n^2 + n \) - \( g_4 : n^3 \) - \( g_5 : \log^2 n \) - \( g_6 : \log n^2 \) - \( g_7 : \log(n!) \) - \( g_8 : 2^{n+1} \) - \( g_9 : \ln \ln n \) - \( g_{10} : 10000 \) - \( g_{11} : \sqrt{n} \) - \( g_{12} : \log \log n \) - \( g_{13} : (n+1)! \) - \( g_{14} : \sqrt{\log n} \) - \( g_{15} : \log \sqrt{n} \) - \( g_{16} : n \) - \( g_{17} : 2^n \) - \( g_{18} : n \log n \) - \( g_{19} : 5n^2 - 13n + 6 \) - \( g_{20} : n / \log n \) **Note:** \( \log n = \log_2 n; \ln n = \log_e n; \log^2 n = (\log n)^2; n! \) is the factorial of \( n \), i.e., \( n! = 1 \times 2 \times \cdots \times n \). Reading the long list, Yihan realized that things were not as simple as she thought. Could you help her with the following problems? For all the questions in this problem, you only need to show your answer without explaining. The only exception is question (4), where you need to show proofs or explanations. 1. What does polylogarithmic mean (use \( O(\cdot), \Omega(\cdot), \omega(\
Transcribed Image Text:Yihan recently learned the asymptotical analysis. The key idea is to evaluate the growth of a function. For example, she now knows that \( n^2 \) grows faster than \( n \). She wants to know whether she really understands the idea, so she has created a little task. First of all, she found a lot of functions here: - \( g_1 : 3^n \) - \( g_2 : n! \) - \( g_3 : n^2 + n \) - \( g_4 : n^3 \) - \( g_5 : \log^2 n \) - \( g_6 : \log n^2 \) - \( g_7 : \log(n!) \) - \( g_8 : 2^{n+1} \) - \( g_9 : \ln \ln n \) - \( g_{10} : 10000 \) - \( g_{11} : \sqrt{n} \) - \( g_{12} : \log \log n \) - \( g_{13} : (n+1)! \) - \( g_{14} : \sqrt{\log n} \) - \( g_{15} : \log \sqrt{n} \) - \( g_{16} : n \) - \( g_{17} : 2^n \) - \( g_{18} : n \log n \) - \( g_{19} : 5n^2 - 13n + 6 \) - \( g_{20} : n / \log n \) **Note:** \( \log n = \log_2 n; \ln n = \log_e n; \log^2 n = (\log n)^2; n! \) is the factorial of \( n \), i.e., \( n! = 1 \times 2 \times \cdots \times n \). Reading the long list, Yihan realized that things were not as simple as she thought. Could you help her with the following problems? For all the questions in this problem, you only need to show your answer without explaining. The only exception is question (4), where you need to show proofs or explanations. 1. What does polylogarithmic mean (use \( O(\cdot), \Omega(\cdot), \omega(\
Expert Solution
Step 1
1)
An algorithm is said to of Poly-logarithmic runtime if
 
 
T(n) =O(log⁡(nk)) (k≠0,1or−1)
 
It implies that the order of time is a logarithmic polynomial logk(n)orlog⁡(nk)
(g5, g6, g7, g9, g12, g14,g15 ,g18 and g20)
 
Explanation
-ln⁡is also short for loge
-if k=0 , its constant time , for n=1 its just logarithmic not polyLog
steps

Step by step

Solved in 3 steps

SEE SOLUTIONCheck out a sample Q&A here
Blurred answer
Knowledge Booster
Bare Bones Programming Language
Learn more about
Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.
Similar questions
Recommended textbooks for you
Database System Concepts
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
C How to Program (8th Edition)
C How to Program (8th Edition)
Computer Science
ISBN:
9780133976892
Author:
Paul J. Deitel, Harvey Deitel
Publisher:
PEARSON
Database Systems: Design, Implementation, & Manag…
Database Systems: Design, Implementation, & Manag…
Computer Science
ISBN:
9781337627900
Author:
Carlos Coronel, Steven Morris
Publisher:
Cengage Learning
Programmable Logic Controllers
Programmable Logic Controllers
Computer Science
ISBN:
9780073373843
Author:
Frank D. Petruzella
Publisher:
McGraw-Hill Education
SEE MORE TEXTBOOKS