1. Engineering
  2. Computer Science
  3. 5 pts what is the worstcase bigo asymptotic running time...

Question: 5 pts what is the worstcase bigo asymptotic running time...

Question details
  1. [5 pts]: What is the worst-case “big-O” asymptotic running time of the following method mthd, assuming that the parameter n is a positive integer? Assume that the time complexity of addition is logarithmic in the magnitude of the number. Justify your answer.

void mthd ( int n ) {

    int answer = 0;

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

        for ( int k = 1; k <= n; k++ ) {

            answer += i + k;

        }         

    }

    for ( int m = 1; m < n; m++ ) {

        answer += m;

    }

}

Solution:

  1. [5 pts]: Consider that f(n) = n + n lg n is Q(n lg n) by applying the definition of Q-complexity from Chapter 3 of Cormen (reproduced below).

Definition: Θ(g(n)) = { f(n) : there exists positive constants c1, c2, n0 such that 0 ≤ c1g(n)f(n)c2g(n) , for nn0}. Find a (c1, c2, n0) triple that meets the criteria. Show some work.

Solution by an expert tutor
Blurred Solution
This question has been solved
Subscribe to see this solution