Reference no: EM13166157

Each of the following are formulas for the number of operations in some algorithm. Express each formula in big-O notation.

• n² + 5n
• 3n² + 5n
• (n + 7 )(n - 2)
• 100n + 5
• 5n + 3n²
• The number of digits in 2n?
• The number of times that n can be divided by 10 before dropping below 1.0?

2. Determine which of the following formulas is O(n):

• 16n³
• n² + n +2
• Ln^2/2
• 10n + 25

3. List the following formulas in order of running time analysis, from greatest to least time requirements, assuming that n is very large:

n^{2 +} 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.

• n³ + n² log₂ n + n³log₂n
• n + 4n²⁺ 4ⁿ
• 48n⁴ + 16n² + log₈ n +2n

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 );