QUIZ ON SPACE AND TIME COMPLEXITY

#1

int count = 0;
for (int i = N; i > 0; i /= 2)
for (int j = 0; j < i; j++)
count++;
a) O(log N)
b) O(N)
c) O(N*log N)
d) O(N^2)

Its answer should be O(LOGN)N , but it is given O(N) here.

#2

hello @CODER_JATIN
For a input integer n, the innermost statement is executed following times.

n + n/2 + n/4 + … 1

So time complexity T(n) can be written as

T(n) = O(n + n/2 + n/4 + … 1) = O(n)

The value of count is also n + n/2 + n/4 + … + 1

#3

and in 2nd question, the first loop will run (N) times, second loop will run maximum (N^2) times, and also 3rd loop will run maximum of (N^2) times, that’s why overall complexity is O(n^5) ???

#4

bro i dont have question,pls share question with me

#5

Q5) Find the Complexity of the given code. int gcd(int n, int m) { if (n%m ==0) return m; if (n < m) swap(n, m); while (m > 0) { n = n%m; swap(n, m); } return n; } PLEASE EXPLAIN THIS QUESTION ALSO?

#6

Q8) To verify whether a function grows faster or slower than the other function, we have some asymptotic or mathematical notations, which is_. a) Big Omega Ω (f) b) Big Theta θ (f) c) Big Oh O (f) d) All of the above ,PLEASE EXPLAIN THIS NOTATIONS ALSO , ( BHAIYA HAS NOT EXPLAINED THESE NOTATIONS.)

#7 
b >= a / 2, then a, b = b, a % b will make b at most half of its previous value

b < a / 2, then a, b = b, a % b will make a at most half of its previous value, since b 
is less than a / 2

So at every step, the algorithm will reduce at least one number to at least half less. In at most O(log2a)+O(log2b) step, this will be reduced to the simple cases. Which yield an O(log2n) algorithm, where n is the upper limit of a and b.

#8

BHAIYA YEH 2ND QUESTION HAI -------->>>>>>> Q) Find the Complexity of the given snippet. void function(int n) { int count = 0; //executes O(n) times for (int i=0; i<n; i++) //Executes 0(n^2) times for (int j=i; j< ii; j++) if (j%i == 0) { //executes O(n^2) times for (int k=0; k<j; k++) System.out.println(""); } }

#9

YAA FIR EK FILE KA LINK SHARE KR DETA HU , USME JO QUESTIONS HAI VO DOUBT HAI , VO BTA DENA FIIR.

#10

yeh tumhara shai tha->

#11

bro first read about these notations and then try this problem.

read this article->link

#12

Q11) lg (n!) = ……………… a) O(n) b) O(lg n) c) O(n^2) d) O(n lg n) , bhaiya yeh bhi batana?

#13

n! = n * (n - 1) * (n - 2) * (n - 3) … 2 * 1
log(n!) = log(n * (n - 1) * (n - 2) * (n - 3) … 2 * 1)
log(n!) = log(n) + log(n - 1) + log(n - 2) + … + log(2) + log(1)
log(n!) = O(log(n) + log(n) + log(n) + … log(n) + log(n))
log(n!) = O(n*log(n))

#14

Q14) Find complexity of the following void pat(){ //executes log (input size) times for (int i = 2; i <=n; i = pow(i, c)) { System.out.print("") } //Here fun is sqrt or cuberoot or any other constant root //executes log n times for (int i = n; i > 1; i = fun(i)) { System.out.print("") } } a) O(N LogN) b) O(N^3) c) O(N^2) d) LogLog N ,please explain this also

#15

Q12) The running time of an algorithm is given by T(n) = T(n - 1) + T(n - 2) - T(n - 3), if n > 3 n, otherwise. a) N b) log n c) n+1 d) None of these…this also?

#16

bro have u tried them on ur own?

#17

hanji bhaiya , yeh questions ni hue they baaki ho gaye

#18

ek baar dobaara try kar leta hu :slight_smile:

#19

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.