Each of the following are formulas for the number of operations in some algorith
ID: 3554836 • Letter: E
Question
Each of the following are formulas for the number of operations in some algorithm. Express each formula in big-O notation.
2. Determine which of the following formulas is O(n):
3. List the following formulas in order of running time analysis, from greatest to least time requirements, assuming that n is very large:
n2 + 1; 50 log n; 1,000,000; 10n + 10,000
4. Do a big O analysis for those statements inside each of the following nested loop constructs.
a. for ( k = 0; k < n; ++k)
for ( j = 6; j < n; ++j)
{
...
}
b. for ( k = 0; k < n; ++k)
{
j = n;
while ( j > 0)
{
...
j / = 2; // integer division
}
}
c. k =1;
do
{
j = 1;
do
{
...
j * = 2;
}
while ( j < n );
++k;
}
while ( k < n );
5. Suppose that each of the following expressions represents the number of logical operations in an algorithm as
a function of n, the number of data items being manipulated. For each expression, determine the dominant term and then classify the algorithm in big-O terms.
6. Consider the following nested loop construct. Categorize its efficiency in terms of the variable n using big-O
notation. Suppose the statements represented by the ellipsis require four main memory accesses (each
requiring one microsecond) and two disk file accesses (each requiring one microsecond). Express in
milliseconds the amount of time this construct would require to execute if n were 1000.
x = 1;
do
{
y = n;
while ( y > 0 )
{
....
--y;
}
x * = 2;
}
while ( x < n * n );
Explanation / Answer
Big O notation implies that the given function will not take time greater than specified in the paranthesis after O.
So O(n^2) means it will take atmost n^2 time units.
Q1 - (1). O(n^2)
(2). O(n^2)
(3). O(n^2)
(4). O(n)
(5). O(n^2)
(6). O(n)
(7). O(n)
Q2 - 10n+25 we ignore constants and lower power as well.
Q3- 1,000,000; 50 log n; 10n + 10,000; n2 + 1;
Q4 - a) O(n^2)
b).O(n log n)
c).O(n log n)
Q5 - a).
b).O(4^n)
c).O(n^4)
Q6- O(n logn)
Log is always used with base 2 here.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.