Class_23_08_2024

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;

}

• 
  O(n²)

• 
  O(n*log(n))

• 
  O(n*log(n*Log(n)))

• 
  O(n)

What is the time complexity of fun()? 
int fun(int n)

{

int count = 0;

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

for (int j = i; j > 0; j--)

count = count + 1;

return count;

}

• Theta (n)

• Theta (n²)

• Theta (n*log(n))

• Theta (n*(log(n*log(n))))

Which of the given options provides the increasing order of asymptotic complexity of functions f1, f2, f3, and f4?

f1(n) = 2ⁿ

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

f3(n) = n*log(n)

f4(n) = n^log(n)

• 
  f3, f2, f4, f1

• f3, f2, f1, f4

• f2, f3, f1, f4

• f2, f3, f4, f1

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++;

}

• O(n*log(n)²)

• O(n*log(n))

• O(n²)

• O(n)

In a competition, four different functions are observed. All the functions use a single for loop and within the for loop, same set of statements are executed. Consider the following for loops: 

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

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

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

D) for(i = n; i <= n; i /= 2)
If n is the size of input(positive), which function is most efficient(if the task to be performed is not an issue)?

• A

• B

• C

• D

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

• 
  X will be a better choice for all inputs

• X will be a better choice for all inputs except possibly small inputs

• X will be a better choice for all inputs except possibly large inputs

• 
  Y will be a better choice for small inputs

In the following function, let n >= m. 
int gcd(n, m)

{

if (n % m == 0)

return m;

n = n % m;

return gcd(m, n);

}

• theta  (log(n))

• Omega  (n)

• theta  (log(log(n)))

• theta  (sqrt(n))

Which of the following is not O(n²)?

• (15) * n²

• 
  n^1.98

• n³/(sqrt(n))

• (20) * n²

What is the time complexity of the following function?
void A (int n)
{
         int i, j, k;
         for (i=1; i<=n; i++)
             {
                  for (j =1; j <=i; j++)
                        {
                              for (k =1; k< = 133; k++)
                                       {
                                             X=Y+Z;
                                        }
                         }
               }
}

• n^3

• nlogn

• n^2

• loglogn

Consider the following function: 
double foo (int n){

int i;

double sum;

if (n = = 0) return 1.0;

else{

sum = 0.0;

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

sum += foo (i);

return sum;

}

}

• O(1)

• O(n)

• O(n!)

• O(nⁿ)