20 Loop Time Complexity Questions with Many Variations | Nested loops | Sachin Mittal sir

Crack GATE Computer Science Exam with the Best Course.

----------------------------------------------------

➤ Join GATEOverflow + GoClasses Combined TEST SERIES for Best Quality questions for GATE CSE Preparation, Here:

----------------------------------------------------
➤Join GATE Overflow & GO Classes #Telegram Groups for GATE CSE Doubt Discussions:

----------------------------------------------------

Complete #Discrete_Mathematics Course(FREE) Link :

Complete #Engineering_Mathematics Course(FREE) Link :

Download GATEOverflow GATE Previous Years Questions(GATE CSE PYQs) Books here:

----------------------------------------------------
Feel free to Contact Us for any query.

➤ GO Classes Contact :
([phone]
([phone]

GO Classes Mail ID :

#gatecse #gate2024 #goclasses #computerscience #computer_science

[bhargavpatel]

Please upload this kind of videos more of every topic. This are very helpful to us ❤

[shaad_iqbal]

Great explanation of the last question (Q.18). 🔥🔥

[nareshk]

for(int j=2;j<n;j=(j*j)){

}
for this loop complexity is log n
5:44

[ml_enthusiast]

never seen a practice set for time complexity like this!!!! Thank u sir :)

[gravity]

Question no. 18 beautifully explained 💯

[syedqasim]

QUESTION # 17


The time complexity for these loops is O(n log n). This is because the outer loop runs log n times, since the variable i is doubled in each iteration. The inner loop runs i times, which is proportional to n in the worst case. Therefore, the total number of operations performed by the loops is:

1 + 2 + 4 + 8 + … + n = (n - 1) + n = 2n - 1

This is O(n) in the worst case. However, since we are using big O notation, we can ignore the constant factors and lower-order terms. Therefore, the time complexity is O(n log n), where log n is the number of times the outer loop runs.

[coldcoke]

the only good video on time complexity on youtube

[ananyakamalapur]

Qn 18 is AMAZE!!! 🔥🔥🔥And sachin sir's expln makes it more amaze!!

[meetthakor]

watching question 18 i was like this is going to be so hard but after understanding it, it was quite good and very good explanation

[killbillpandey-pm]

please make a video on log-related terms in time complexity topics like a log, logn, loglogn, loglogn^2 etc. very confusing which one is bigger/smaller.

[milidubey]

For question 18, i is running n times, jth loop is running n^2 times and can we say that condition
is true for multiples of i hence kth loop runs no.of multiples between 0 and n^2 times ?

So, if we assume for i=m,
ith loop runs 'm' times
jth loop runs 'm^2' times
and kth loop runs 'm+1' times where m+1 is no.of multiples between 0 and m^2
hence time complexity is m*(m^2)*(m+1)
=(m^4) + 1 is equal to m^4

Is this correct ?

[alpeshpatel]

51:00 Better to specify in question that "^" is "raised to" or "power" operator. Because in C language ^ is bitwise XOR.

[devbhattdev]

13th question meh if we write i*=2 toh n time keh liye loop will run logn time naa so inner loop will anyways gonna run like 1+2+3+4+5....logn so it's an AP so why not the tc will be logn square.

[motivationalkk]

sir we are dividing the updation loop in question 3 so Time complexity is the log base 3

[m_lan____]

10:18 No sir they are still using that old version... :)

[guruguruji]

Amazing session as always. Upload notes please.

[priyanshushekhar]

sir 14:10 ...for inner loop Kya i = 1 ke liye loop chalega ....is it possible ?

[PymonPanics]

Sir in Q-1 Both loops are independant of each other, Shouldn't it be SquareRoot(n)

[sohelansari-dqkv]

Sir u should explain how you are getting logn, n, √n .... U are explaining directly u are saying it will this and this... It's very difficult for the beginner's

[ankitagrawal]

Sir Can u add pdf without annotation so that firstly we could try from our side