Help.. For this, you will solve problems related to efficiency, and the Big O as

Question

Help.. For this, you will solve problems related to efficiency, and the Big O asymptotic notation. SHOW YOUR WORK.

The definition of Big O

Let f(n) and g(n) be functions mapping positive integers to positive real numbers.
We say that f(n) is O(g(n)) if there is a real constant c > 0 and an integer constant N ? 1 such that:

f(n) ? c * g(n), for n ? N

Note that the constants c and n0 are not unique. You just have to find a c and an N that satisfies the definition of Big O

3.1 Given a time function, T(n) = 3x2 + 5x + 2, find constants c and N that prove that the big O of the growth function T(n) is n2

3.2 Find the Big O of T(n) = 4x3 + 12x2 + 2x + 12. Justify your answer by finding constants c and N

3.3 Find the Big O of the following code:

for(int i = 0; i < n; i++) {

for(int j = 0; j < n; j++) {

System.out.println(“Hello!”);

}

}

You do not have to find a T(n), or c and N. Just give the Big O, and informally justify your answer.

Explanation / Answer

3.3 Big O for this code is O(n^2).

outer for loop runs n times. For every interation of outer loop inner loop runs n times so total it runs n^2 times.

3.1 For c=6 and N=2 Big O function satisfies i.e., 24<=24

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

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