If f(n) = n 2 , then: f(n) is O(n) f(n) is O(n 2 ) f(n) is O(n) f(n) is O(n*log

Question

If f(n) = n2, then:

f(n) is O(n)

f(n) is O(n2)

f(n) is O(n)

f(n) is O(n*log n)

Suppose that the running time of a function f(int n) is given by the formula
100*n2+2*n-3. Then the time complexity of f(n) is:

O(n)

O(n2)

O(1)

O(0)

T/F: Suppose that, for a length-n array, the sorting algorithm A has a time complexity of O(n2) and the sorting algorithm B has a time complexity of O(n*log n).

Then B always sorts any array faster than A.

Suppose freq(n) is the number of times the statement S is executed in the following code fragment:

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

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

               S;

Then the time complexity of freq(n) is:

O(1)

O(n)

O(n*log n)

O(n2)

Same as the previous problem, but the code fragment is:

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

       for (int j=0; j < i; j++)

           S;

Then the time complexity of freq(n) is:

O(1)

O(n)

O(n*log n)

O(n2)

Same as the previous two problems, but the fragment is:

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

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

         S;

Then the time complexity of freq(n) is:

O(1)

O(log n)

O(n)

O(n2)

Same as the previous three problems, but the fragment is:

    for (int i=0; i < n; i = i*2)

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

           S;

Then the time complexity of freq(n) is:

O(1)

O(n)

O(n*log n)

O(n2)

Suppose that A is an array of length n, containing some permutation of the integers 1..n.

Also suppose that the running time T(A) of a method processArray(int[] A) is equal to the value of A[0].

Then the worst case time complexity of the method is:

O(1)

O(log n)

O(n)

None of the above.

Assume the same definitions as the previous problem.

Then the best case time complexity of the method is:

O(1)

O(log n)

O(n)

O(n2)

Assume the same definitions as the previous two problems.

If we assume that each of the possible values of A is equally likely, then the average case time complexity of the method is:

O(1)

O(log n)

O(n)

O(n2)

T/F: The average run time of some method over all possible inputs n may be greater than the worst case run time for the same method.

If f(n) is O(g(n)), then g(n) is always:

O(f(n))

(f(n))

(f(n))

None of the above.

T/F: An algorithm with exponential time complexity O(2n) is better than one with O(n100) for large n.

One reason we may use sequential search instead of binary search to find a specific element within an array R is:

It is difficult to implement binary search correctly.

R may always be sorted.

R may always be unsorted.

There is no reason: we should always use binary search instead of sequential search.

The worst-case performance of binary search within an array of length n:

Has the same time-complexity as its best-case performance.

Has the same time-complexity as its average performance.

Has a time complexity of O(log n).

More than one of the above answers is true.

f(n) is O(n)

f(n) is O(n2)

f(n) is O(n)

f(n) is O(n*log n)

Explanation / Answer

If f(x)=x^2 then f(x) is O(x^2)
The time complexity of 100x2+2x-3 is O(x2) <--- it is always the biggest polynomial (constants drop out)

Then B always sorts any array faster than A. FALSE

freq(n) is O(n2) <--- keep in mind the polynomial inside the O(...) can be anything bigger than the function's runtime. i.e. freq(n) is also O(n200), O(...) just provides and upper bound that says the function will not be greater than this as x->infinity

all the freq's are O(n2) however the last one is also O(nlogn), which is more accurate and probably the answer your teacher wants

Suppose that A is an array of length n, containing some permutation of the integers 1..n.

Also suppose that the running time T(A) of a methodprocessArray(int[] A) is equal to the value of A[0].

Then the worst case time complexity of the method is: this is phrased awkwardly and you never say what T(A) is, but if it helps, arrays have O(1) accessing time, so A[0] has complexity O(1).

The average run time is generally the worst run time, short of quicksort and a couple other algorithms where average time is better than worst time

False (I'm pretty sure)

If f(n) is O(g(n)), then g(n) is always: (f(n))

T/F: An algorithm with exponential time complexity O(2n) is better than one with O(n100) for large n. False

You can only use binary search when R is sorted, you use sequential searches when R is not necessarily sorted every time.

The worst-case performance of binary search within an array of lengthn: all of the above are true

Hope this helped, next time you should consider numbering your questions.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

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