Assume that each of the expressions in the following table has processing time T(n) to solve a problem of size n. Identify the dominant term(s) having the growing increase in n and specify the Big-Oh complexity. Expression Dominant term(s) Big-Oh A.1 8 + 0.081n2 + 0.040n A.2 100 + n log2 n A.3 100n + 0.081 log3 n + n3 A.4 0.081 log4 n + 81n Find the Big-Oh for each of the following programs. B.1 sum = 0; for(i = 0; i < n; i++) sum++; B.2 sum = 0 for(i = 0; i < n; i++) for( j = 0; j < n * n; j++) sum++;
Assume that each of the expressions in the following table has processing time T(n) to solve a problem of size n. Identify the dominant term(s) having the growing increase in n and specify the Big-Oh complexity. Expression Dominant term(s) Big-Oh A.1 8 + 0.081n2 + 0.040n A.2 100 + n log2 n A.3 100n + 0.081 log3 n + n3 A.4 0.081 log4 n + 81n Find the Big-Oh for each of the following programs. B.1 sum = 0; for(i = 0; i < n; i++) sum++; B.2 sum = 0 for(i = 0; i < n; i++) for( j = 0; j < n * n; j++) sum++;
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
Assume that each of the expressions in the following table has processing time T(n) to solve a problem of size n. Identify the dominant term(s) having the growing increase in n and specify the Big-Oh complexity.
|
Expression |
Dominant term(s) |
Big-Oh |
A.1 |
8 + 0.081n2 + 0.040n |
|
|
A.2 |
100 + n log2 n |
|
|
A.3 |
100n + 0.081 log3 n + n3 |
|
|
A.4 |
0.081 log4 n + 81n |
|
|
- Find the Big-Oh for each of the following programs.
B.1 sum = 0;
for(i = 0; i < n; i++)
sum++;
B.2 sum = 0
for(i = 0; i < n; i++)
for( j = 0; j < n * n; j++)
sum++;
Expert Solution
![](/static/compass_v2/shared-icons/check-mark.png)
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
Step by step
Solved in 2 steps
![Blurred answer](/static/compass_v2/solution-images/blurred-answer.jpg)
Follow-up Questions
Read through expert solutions to related follow-up questions below.
Follow-up Question
Very appreciate
but what about this point
0.081 log4 n + 81n?
Solution
Follow-up Question
|
Expression |
Dominant term(s) |
Big-Oh |
A.1 |
8 + 0.081n2 + 0.040n |
|
|
A.2 |
100 + n log2 n |
|
|
A.3 |
100n + 0.081 log3 n + n3 |
|
|
A.4 |
0.081 log4 n + 81n |
|
|
here this table incomplete?
Solution