Big-O problems: 1.) Given an algorithm with time complexity f(n) = n^2. It is co

Question

Big-O problems:

1.) Given an algorithm with time complexity f(n) = n^2. It is coded up in C++ and executed on your computer. It takes t seconds to run on n inputs. Running the same program on a computer 64 times faster than yours, how many inputs could be processed in the same amount of time?

2.) Find the smallest integer c that makes this statement true: sqrt^(n) = O(n^c).

3.) Show that if p(n) is a polynomial in n, then log p(n) is O(log n). Hint: Start with the equation for the generic form of a polynomial.

4.) Show that n is O(log n).

5.) An array R contains n elements. Algorithm S calls Algorithm T on each element in R. Algorithm T performs i basic operations on element R(i). What is the worst-case running time of Algorithm S?

6.) Find the big-O for these code fragments. All variables are ints.

A) sum = 0;

for (i = 1; i <= 10; i++)

sum++;

B) sum = 0;

for (i = 1; i < n*n; i++)

sum++;

C) sum = 0;

for (i = 1; i <= n; i++)

for (j = 1; j <= n; j *= 2);

sum++;

Explanation / Answer

1)Given algorithm complexity f(n) = n^2

so the code will execute in t sec

the it can process 64 inputs in that given time.

2)The smallest integer is 2.

3)

Related Questions

Navigate

• Browse (All)
• Browse B
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.