What is the time complexity T(n) of the following program?

a)
int n, d, i, j;
cin >> n;
for (d=1; d<=n; d++)
for (i=1; i<=d; i++)
for (j=1; j<=n; j += n/10)
cout << d << " " << i << " " << j << endl;


b)
void main()
{ int n, s, t;
cin >> n;
for (s = 1; s <= n/4; s++)
{t = s;
while (t >= 1)
{ cout << s << " " << t << endl;
t--;
}
}
}


c)
void main()
{ int n, r, s, t;
cin >> n;
for (r = 2; r <= n; r = r * 2)
for (s = 1; s <= n/4; s++)
{
t = s;
while (t >= 1)
{
cout << s << " " << t << endl;
t--;
}
}
}




Answers were Sorted based on User's Feedback



What is the time complexity T(n) of the following program? a) int n, d, i, j; cin >> n; ..

Answer / arunthathi

1.t(n)=10*n*n*(n+1)/2
2.t(n)={n/4*(n/4)*[(n/4)+1]}/2

Is This Answer Correct ?    17 Yes 6 No

What is the time complexity T(n) of the following program? a) int n, d, i, j; cin >> n; ..

Answer / rajesh kumar pal

a- (n*n)*log(n).
b- log(n)*log(n).
c-log(n)*log(n)*log(n).

Is This Answer Correct ?    5 Yes 9 No

What is the time complexity T(n) of the following program? a) int n, d, i, j; cin >> n; ..

Answer / hero

a. T(n)= n*(2n+1)/2*n/10

Is This Answer Correct ?    2 Yes 7 No



Post New Answer



More C++ Code Interview Questions

write a c program, using for loop, that accepts and odds two numbers. The output must be the sum and the addens. This should be repeated 5 times while the first number is decremented by one and the second number is incremented by 1.

2 Answers   Infosys, IBM,


How can I Draw an ellipse in 3d space and color it by using graph3d?

0 Answers  


. Remove all the blank spaces between character.Matrix is of 10* 10. eg: INPUT ------------------------------------ | N | A | | V | |T ------------------------------------- | |G | U | |P | -------------------------------------- |T | | | A | | ------------------------------------ OUTPUT: ------------------------------------ | N | A | V | T | | ------------------------------------- |G |U | P | | | -------------------------------------- |T | A | | | | ------------------------------------

2 Answers   Nagarro,


Algorithm in O(2n) Presently we can solve in our hypothetical machine problem instances of size 100 in 1 minute using algorithm A, which is a O(2n). We would like to solve instances of size 200 in 1 minute using algorithm A on a new machine. What is the speed of the new machine should be?

2 Answers   ABC, Qatar University,


write a function that reverse the elements of an array in place.The function must accept only one pointer value and return void.

0 Answers   HCL, SRCASW,






Deriving time complexity of Binary tree and AVL tree, step by step.

4 Answers   NetApp,


We need to write the function to check the password entered is correct or not based on the following conditions.. a) It must have atleast one lower case character and one digit. b)It must not have any Upper case characters and any special characters c) length should be b/w 5-12. d) It should not have any same immediate patterns like abcanan1 : not acceptable coz of an an pattern abc11se: not acceptable, coz of pattern 11 123sd123 : acceptable, as not immediate pattern adfasdsdf : not acceptable, as no digits Aasdfasd12: not acceptable, as have uppercase character

0 Answers  


Find the maximum product of three numbers in an array? Eg. 9,5,1,2,3 Max product= 9*5*3= 135 The array can hav negative numbers also..

7 Answers   CTS,


Implement a command console for changing settings on a particular object. The command console should allow you to enter a string and will return the response (very similar to a terminal session). The commands are as follows: SET propertyname=newvalue will change the target object’s member named “propertyname” to have a value equal to “newvalue”. If the input value is incompatible (i.e. an int being set to a string), print out an appropriate error message. GET propertyname will print out the current value of the target object’s member named “propertyname”. GET * will print out a list of all target object members and their current values. The system should be extensible for future commands and should accept an arbitrary object, such that another developer could insert another object into the system and rely on the command console to get and set the properties correctly.

0 Answers   ABC, Guidance Software,


Write a program that takes a 3 digit number n and finds out whether the number 2^n + 1 is prime, or if it is not prime find out its factors.

2 Answers   TCS,


A suduco given & u hv 2 check if it is incomplete(blanks left),or correct or incorrect

0 Answers  


hello friends, given an expression we have to remove the unwanted brackets in that expression. Eg : (a+b) ---> a+b (a+b)*(c)-----> (a+b)*c. Please mail me if you know the logic. My mail id is : saravana6m@gmail.com. Thank you in advance :-)

1 Answers   GrapeCity, Microsoft,






Categories