1)What is the time complexity of each of the following functions? Explain your a

Question

1)What is the time complexity of each of the following functions? Explain your answers.

int f1(int n)
{
      int count = 0;

      for (int i = n; i > 0; i /= 2)
            for (int j = 0; j < i; j++)
                  count += 1;

      return count;
}

int f2(int n)
{
      int count = 0;

      for (int i = 0; i < n; i++)
            for (int j = i; j > 0; j--)
                  count += 1;

      return count;
}

void f3(int n, int arr[])
{
      int i = 0, j = 0;

      for (; i < n; ++i)
            while (j < n && arr[i] < arr[j])
                  j++;
}

void f4(int n)
{
      int i, x=0;

      for (i = 1; i <= n; i++)
            if (i % 2 == 1)
                  x++;
}

2)Order the following functions in increasing order of asymptotic complexity. Explain your answer.

f1(n) = 2^n

f2(n) = n^(3/2)

f3(n) = nlogn

f4(n) = n^(logn)

3)What is the time complexity for each of the following for loops? Explain your answers.

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

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

(C) for (int i = 1; i < n; i *= 2)

(D) for (int i = n; i > -1; i /= 2)

  

4)What does it mean when we say that an algorithm X is asymptotically more efficient than Y?

5)Big-O notation is used to classify running-time functions. If f(n) is O(g(n)) then f(n) is within a constant factor of g(n).

Definition: Let f(n) and g(n) be two functions on positive integers. We say f(n) is O(g(n)) if there exist two positive constants c and k such that f(n) <= cg(n) for all n >= k.

For each of the following algorithms, show that f(n) is O(g(n)):

f(n) g(n) f(n) = 10n + 5 g(71) = n f(n) = 3n2 +4n + 1 g(n) = n2 n f(n) = 4n3 + 10n2 + 3n-100 g(n) = n3 f(n) = n4 + 7n+ 12 g(71) = n no 541 72 0774 134n

Explanation / Answer

Answer:

2)

F1>f4>f2>f3

To solve these questions take two function compare them , put the value higher value of n and check the range that is it.

Answer:

3)

(A) for (int i = 0; i < n; i++) , this will be O(n) as n runs from 0 to n

(B) for (int i = 0; i < n; i += 2), this will be O(n) , n times

(C) for (int i = 1; i < n; i *= 2) , this will be O(logn) as the n is multiplied with 2 after each iteration

(D) for (int i = n; i > -1; i /= 2) , this is also O(logn) , as n is divided each iteration by 2.

Answer:

4)

f(n) = 10n + 5 , g(n) = n

In big O notation , f(n) = O(g(n)) if g(n) will be the heighest power of n in f(n) , here heighest power of f(n) = 10n + 5 , therefore O(10n) = O(n) = O(g(n)

f(n) = 3n^2 + 4n + 1 , g(n) = n^2

Here heighest power of f(n) is 3n^2

=> O(3n^2) = O(n^2) = O(g(n))

Similarly for all other cases.

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

---

---

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