Scribd
Upload
29 views1 page

Questions Event ADA

The fun(int n) function has a time complexity of O(log n) as the outer for loop runs log n times with each iteration of the inner loop taking constant time. The fun(int n, int arr[]) function has a time complexity of O(n) as the outer for loop iterates n times with the inner while loop taking constant time in each iteration. The gcd(n,m) function has a recursive time complexity of O(log n) as it recursively calls itself with the second argument reduced by at least half each time until it becomes zero. The Mystery(n) algorithm computes the sum of squares from 1 to n. Its basic operation is addition and multiplication,

Uploaded by

thatisthat
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
29 views1 page

Questions Event ADA

The fun(int n) function has a time complexity of O(log n) as the outer for loop runs log n times with each iteration of the inner loop taking constant time. The fun(int n, int arr[]) function has a time complexity of O(n) as the outer for loop iterates n times with the inner while loop taking constant time in each iteration. The gcd(n,m) function has a recursive time complexity of O(log n) as it recursively calls itself with the second argument reduced by at least half each time until it becomes zero. The Mystery(n) algorithm computes the sum of squares from 1 to n. Its basic operation is addition and multiplication,

Uploaded by

thatisthat
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 1

Question 5

What is time complexity of fun()?


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

Question 8
What is the time complexity of the below function?
void fun(int n, int arr[])
{
    int i = 0, j = 0;
    for(; i < n; ++i)
        while(j < n && arr[i] < arr[j])
j++;
}

Question 9

In the following C function, let n >= m.

int gcd(n,m)
{
  if (n%m ==0) return m; 
  n = n%m;
  return gcd(m, n);
}

Question 10
Consider the following algorithm.
ALGORITHM Mystery(n)
//Input: A nonnegative integer n
S ←0
for i ←1 to n do
S ←S + i ∗ i
return S
a. What does this algorithm compute?
b. What is its basic operation?
c. How many times is the basic operation executed?
d. What is the efficiency class of this algorithm?

You might also like