Bissoy.com
Doctors Medicines MCQs Q&A

Consider the following code snippet. It accepts a positive integer n as input. int i = 0. j = 0, val = 1; for (i = 1; i <= n; i++) {      j = n;      if (i% 2 == 0)    {        while (j > 1)      {         val = val * j;          j = j /2;      }    } } What is the worst-case time complexity of the algorithm?

Consider the following code snippet. It accepts a positive integer n as input. int i = 0. j = 0, val = 1; for (i = 1; i <= n; i++) {      j = n;      if (i% 2 == 0)    {        while (j > 1)      {         val = val * j;          j = j /2;      }    } } What is the worst-case time complexity of the algorithm? Correct Answer O(n log n)

The correct answer is option 2.

Concept:

The worst-case time complexity indicates the longest running time performed by an algorithm given any input of size n, and thus guarantees that the algorithm will finish in the indicated period of time.

Program: 

int i = 0. j = 0, val = 1;

for (i = 1; i <= n; i++)          // Loop one

{

          j = n;

          if (i% 2 == 0)

          {

               while (j > 1) {                  // Loop two.

                                     val = val * j;

                                       j = j /2;

                                      }

            }

}

Loop one runs n times (i=1 to i=n) So it takes O(n) time for "i" value  Loop two runs.

Loop two runs like initially J=n, n/2, n/4, n/8, n/16, ...

when Loop two condition becomes n/2k< 1 then stop the Loop two.

2k = n

take to log on both sides.

k= log n

So Loop two runs O(log n) times. 

For each, I value o(log n) times run the program. So for all n value takes n log n time.

Hence the correct answer is O(n log n).

Related Questions

What will be output of the following c program ? #include int main() { int max-val=100; int min-val=10; int avg-val; avg-val =( max-val + min-val ) / 2; printf( "%d", avg-val ); return 0; }
What is the output of following program? abstract class Sum { public abstract int sumOfTwo(int n1, int n2); public abstract int sumOfThree(int n1, int n2, int n3); public void disp( ){ System.out.println("Method of class Sum"); } } class DemoAbstract1 extends Sum { public int sumOfTwo(int num1, int num2) { return num1+num2; } public int sumOfThree(int num1, int num2, int num3) { return num1+num2+num3; } public static void main(String args[ ]){ Sum obj = new DemoAbstract1( ); System.out.println(obj.sumOfTwo(3, 7)); System.out.println(obj.sumOfThree(4, 3, 19)); obj.disp( ); } }
Which two classes use the Shape class correctly?
A. public class Circle implements Shape { private int radius; }B. public abstract class Circle extends Shape { private int radius; }C. public class Circle extends Shape { private int radius; public void draw(); }D. public abstract class Circle implements Shape { private int radius; public void draw(); }E. public class Circle extends Shape { private int radius; public void draw() { /* code here */ } }F. public abstract class Circle implements Shape { private int radius; public void draw() { /* code here */ } }
Which of the following is an external variable in the following C code?
#include int func (int a){ int b; return b;}int main(){ int c; func (c);}int d;
What will be the final values of i and j in the following C code?
#include int x = 0;int f(){ if (x == 0) return x + 1; else return x - 1;}int g(){ return x++;}int main(){ int i = (f() + g()) | g(); //bitwise or int j = g() | (f() + g()); //bitwise or}
What will be the final values of i and j in the following C code?
#include int x = 0;int f(){ if (x == 0) return x + 1; else return x - 1;}int g(){ return x++;}int main(){ int i = (f() + g()) || g(); int j = g() || (f() + g());}
What is the output of this program ? #include
using namespace std;
int n(char, int);
int (*p) (char, int) = n;
int main()
{
(*p)('d', 9);
p(10, 9);
return 0;
}
int n(char c, int i)
{
cout << c << i;
return 0;
}
Comment on the following 2 C programs.
#include  //Program 1int main(){ int a; int b; int c;}#include  //Program 2int main(){ int a; { int b; } { int c; }}
Consider the following C function in which size is the number of elements in the array E: int MyX(int *E, unsigned int size) {       int Y = 0;       int Z;       int i, j, k;       for(i = 0; i < size; i++) Y = Y + E[i];       for(i = 0; i < size; i++) for(j = i; j < size; j++) {       Z = 0;       for(k = i; k <= j; k++) Z = Z + E[k];       if (Z > Y) Y = Z; }       return Y; } The value returned by the function MyX is the
What will happens if the statement free(a) is removed in the following C code?
#include#includemain(){ int *a; a=(int*)malloc(sizeof(int)); *a=100; printf("*a%d",*a); free(a); a=(int*)malloc(sizeof(int)); *a=200; printf("a%p",a); *a=200; printf("a%d",*a);}