of g(x), c, 5 and k) in the next section. For the following code segments below, count the operations and produce a corresponding polynomial representation.
of g(x), c, 5 and k) in the next section. For the following code segments below, count the operations and produce a corresponding polynomial representation.
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
Related questions
Question
![of g(x), c, 5 and k) in the next section. For the following code segments below, count the operations and
produce a corresponding polynomial representation.
f(x) =
public static boolean isEmpty() {
return head == null;
}
f(x)
public static int num_occurrences(int n) {
int count = 0;
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
if( i == j ) continue;
if(strings [i]
count++;
}
}
}
return count;
}
strings[j]) {
==
f(2)
public static void c(int n) {
for(int a = 0; a < n; a++) {
System.out.println( a
}
num_occurrences(n);
}
* a);
f(x)
public static boolean isPrime(int n) {
if(n
1) return false;
==
for(int i = 2; i <n; i++) {
if( n % i == 0 ) {
return false;
}
}
return true;
}
Demonstrating | f(x) | < c| g(x) | for all n > k
For each of the polynomials above, pick a reference function (g(x)) and constants c,k such that the
g(x) bounds f(x) in the most succinct terms possible for Big O.](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2Fa426d8d0-2bb0-421c-8768-59095f46a7fa%2Fc84158c2-cec2-4af0-bd46-279976f83a79%2Fhkmw57k_processed.jpeg&w=3840&q=75)
Transcribed Image Text:of g(x), c, 5 and k) in the next section. For the following code segments below, count the operations and
produce a corresponding polynomial representation.
f(x) =
public static boolean isEmpty() {
return head == null;
}
f(x)
public static int num_occurrences(int n) {
int count = 0;
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
if( i == j ) continue;
if(strings [i]
count++;
}
}
}
return count;
}
strings[j]) {
==
f(2)
public static void c(int n) {
for(int a = 0; a < n; a++) {
System.out.println( a
}
num_occurrences(n);
}
* a);
f(x)
public static boolean isPrime(int n) {
if(n
1) return false;
==
for(int i = 2; i <n; i++) {
if( n % i == 0 ) {
return false;
}
}
return true;
}
Demonstrating | f(x) | < c| g(x) | for all n > k
For each of the polynomials above, pick a reference function (g(x)) and constants c,k such that the
g(x) bounds f(x) in the most succinct terms possible for Big O.
![public static void main(String[] args) {
for(int a = 0; a < n; a++) //n
foo(); //n
}
public static foo() {
for(int a = 0; a < n; a++) //n
System.out.println(a);
}
Log Exponent Rule: Consider the following logarithm a(x) = log2 X°. Note that we can rewrite
this using the "log roll" as c * log2 X. Since constants are factored out during asymptotic analysis,
you can simply drop the constant multiplier (which on a log is it's exponent).
• Example f(x) = log2 X6
f(x) becomes6 * log2 X, and O(log2 X)
Log Base Rule: You may omit the base of the log and assume its base-2.
Transitivity: if a < b< c, then a < c. Related to big , if a = 5x² + 3xand I'm trying to prove that
a is less than or equal to (i.e, bounded by) x2, we would write5x? + 3x < c * x2 and find some
pair of c, k such that this relationship holds. Using transitivity,
5x? + 3x <c* x2
5æ? + 3x < 5a² + 3x? <c * x2
o 5a? + 3x < 8x? <c * x2
· Now simply choose c ==8 and k==1
Estimating g(x) Given f(x)
In the following section, indicate what reference function (g(x)) we should use when attempting to
prove that f(x) is O(g(x)). Use the rules and reference functions above to guide you.
1. f(x) = n+ log2n
2. f(x) = n² + log nº
3. f(x) = n? * n3
4. f(x) = n° /n²
5. f(2) — п * (log n) *п
6. f(x) = n+n log n + log n
Counting Operations to Produce Polynomials
In the following section, I will present you with multiple different bodies of code, and it is your job to
analyze each code section and build a polynomial that represents the number of abstract operations the
code performs. Once we're done here, we'll have built a polynomial that we will analyze further (in terms](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2Fa426d8d0-2bb0-421c-8768-59095f46a7fa%2Fc84158c2-cec2-4af0-bd46-279976f83a79%2Flabbt2_processed.jpeg&w=3840&q=75)
Transcribed Image Text:public static void main(String[] args) {
for(int a = 0; a < n; a++) //n
foo(); //n
}
public static foo() {
for(int a = 0; a < n; a++) //n
System.out.println(a);
}
Log Exponent Rule: Consider the following logarithm a(x) = log2 X°. Note that we can rewrite
this using the "log roll" as c * log2 X. Since constants are factored out during asymptotic analysis,
you can simply drop the constant multiplier (which on a log is it's exponent).
• Example f(x) = log2 X6
f(x) becomes6 * log2 X, and O(log2 X)
Log Base Rule: You may omit the base of the log and assume its base-2.
Transitivity: if a < b< c, then a < c. Related to big , if a = 5x² + 3xand I'm trying to prove that
a is less than or equal to (i.e, bounded by) x2, we would write5x? + 3x < c * x2 and find some
pair of c, k such that this relationship holds. Using transitivity,
5x? + 3x <c* x2
5æ? + 3x < 5a² + 3x? <c * x2
o 5a? + 3x < 8x? <c * x2
· Now simply choose c ==8 and k==1
Estimating g(x) Given f(x)
In the following section, indicate what reference function (g(x)) we should use when attempting to
prove that f(x) is O(g(x)). Use the rules and reference functions above to guide you.
1. f(x) = n+ log2n
2. f(x) = n² + log nº
3. f(x) = n? * n3
4. f(x) = n° /n²
5. f(2) — п * (log n) *п
6. f(x) = n+n log n + log n
Counting Operations to Produce Polynomials
In the following section, I will present you with multiple different bodies of code, and it is your job to
analyze each code section and build a polynomial that represents the number of abstract operations the
code performs. Once we're done here, we'll have built a polynomial that we will analyze further (in terms
Expert Solution
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
This is a popular solution!
Trending now
This is a popular solution!
Step by step
Solved in 4 steps
Knowledge Booster
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.Recommended textbooks for you
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)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
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)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
C How to Program (8th Edition)
Computer Science
ISBN:
9780133976892
Author:
Paul J. Deitel, Harvey Deitel
Publisher:
PEARSON
Database Systems: Design, Implementation, & Manag…
Computer Science
ISBN:
9781337627900
Author:
Carlos Coronel, Steven Morris
Publisher:
Cengage Learning
Programmable Logic Controllers
Computer Science
ISBN:
9780073373843
Author:
Frank D. Petruzella
Publisher:
McGraw-Hill Education