Algorithms | Time and Space Analysis | Time complexity Analysis of iterative programs | RBR 

+Rahul CarLos yeah that explains the 119% :P

Lol :D There r times when i attend both college and this channel..

+Danial Janboura You must have the same habits, when the correct answer is 109% and not 119%

HAAHAHAHAHAHAHAHAHA sucha a nice conversation i am very careful here not to make mistake

Hazrat Bilal .... such a not sucha a

Hahahaha :p

You wrote it opposite.

O(n to 2)

I assume that you are asking how n^2 is coming. For each i in 0

In the 1st iteration i will be 1 and J will be 1 too and for each value of i J will run exactly N times so the time complexity will be O(N^2)

no it can't be evrytime as for the next loop j will run n-2 times since j=i;

Don't know it myself. But I think it has something to do with dominant k. Since k^2 is dominant to k, you remove the excess. I saw this in one of the hacker-ranks video about BIG O notation.

k^2 + k > n/2 for tightest upper bound k^2 >n k>sqrt(n) k=O(sqrt(n))

Thanks

If K>sqrt(n) Doesn't that mean that K is the upper bound of sqrt(n)? sqrt(n) = O(k)...

@@ram-tv5701 No. K= O(√n) means that K0 and n>=n0, for some n0>=1

After analyzing your code, your code can be simplified into: 1) `count` can be safely remove (No dependency) 2) Converting the inner while loop into for loop(For sake of understanding) count = 0 for(i=N; i>0; i- -): for(j=i; j>0; j/=2): count += j Dry Run: ======= When i=N, j executes log2(N+1) times ([26:50] but upto j>=1) When i=N-k, j executes log2(N-k+1) times When i=1, j executes log2(1+1) times Execution ======= = log2(N+1) + log2(N) + ... + log2(N-k+1) + ... + log2(2) = log2[ (N+1) . (N) . ... (N-k+1) ... . 2] = log2[ (N+1)! ] = log2(N!) Time Complexity ======== As we know that O(N!) = O(N^N) Therefore, = log2(N!) = O ( log2(N^N) ) = O (N. Log2(N)) Hence the Time complexity will be O(N.logk(N)) where k = 2 For eg. if N = 4, then in worst case the loop will execute 8 times if N = 16, then in worst case the loop will execute 64 times and so on Verification ======= loop = 0 count = 0 for(i=N; i>0; i- -): for(j=i; j>0; j/=k): count += j loop++ The value of loop will always be less than O(N.logk(N))

omg its a place where suda murthy came from it is a place where alumini are studious not like my college who has actors , cricketers and shit

Do you know which batch?

Google wants to know your location

While the typical college professor takes about O(n^n)

@@yoowon-hye9270 More like (n factorial)

@@yoowon-hye9270 infinity, you can say.

+BaSkA I 100% agree with you the same happened to me lol

sad life bro

+BaSkA unfortunately yeap by the way sis not bro lol

Mira Nadja sorry sis, send show some pics tho.

+BaSkA no need to apologize bro.. I thought from my name is clear... obviously is not known in your country lol

From which university

Same doubt! Anybody clarify?

@@anushaboina6237 he multiplied j value to k at every iteration i.e 1*100,2*100,3*100........n*100 and for first loop executive only 1 time for each iteration ,so no need to bother about multiple of 1 i.e 1*1*100,1*2*100,...... 1*n*100

same question. Im thinking for that one he didn't do overall complexity but for each for loop?

Good luck from India

I might be a bit late, but this is his website: ravindrababuravula.com/

bro follow durga sir

Yeah because [log(base a) n] is typically [log n / log a] so log a here being a constant can be ignored...hence we can write O(log(n)), without mentioning the base

Can someone explain this

@@foodie_traveller_motorhead mee too wants this !!

the log n definition is like this

i know its late but i dont think so the expansion of log is this !

I suppose he meant natural logarithm (ln n)

stackoverflow.com/questions/25905118/finding-big-o-of-the-harmonic-series. Check this out

refer to 12 standard mathematics book

Same question arises to me …. If you got the answer please reply here. Thanks

he calculated every iteration i separately and then added all of the iterations. the method you considered calculated the time complexity for all the steps till i.So,you should not add them in the end.Just calculate when i=n which is order of n^2.

for better understanding the inner most for loop can be considered as a constant, like u can remove that inner for loop with 100 times printf(ravi) written now we will end up with only 2 loops and their is no way to achieve n^3 with only two loops.

karthik prasad you r getting confused between the no. of time the program is getting executed and the no. Of times the printf statement is getting executed.. Yes the no. of times the entire program is being executed is of order n^3.. Bt the p. f statement, the no. Of times the 2 inner loop getting executed counts...

"" if "i" runs 2 times, "j" runs 2*2 times(2 times for each time of i i.e 2*2) and k runs 2*2*100 times, if "i" runs 3times, "j" runs 3*3 times and k runs 3*3*100 times. "" this would be true only when it would be for ( int i=0; i

"Now I have become courageous..."

Vivian, LoL.

malayali?

Solve the quadratic equation in k. You get k in terms of sqrt(n).

kaise

juhi singh K^2 +k>2n K>( -1+sqrt(1+8n))/2

k^2 + k > n/2 for tightest upper bound k^2 >n k>sqrt(n) k=O(sqrt(n))

The highest power in the expression generally dominates/determines the Order. In this case the highest power of k is 2. Now, solve the inequality to express it in terms of k for the dominant term (i.e. the 2nd power). You'll end up with : k > sqrt(n)

its a formula for sum of n natural numbers

Your teacher so bad.hahaha

1/n cannot be a constant

i guess u r right @satyam but the answer should be O(n^2(log n))

you are right bro. but for calculating time complexity we exclude constant term. that is why he took n/2 only.

+Vaibhav Kumar you are missing the values initialized. before entering the loop, the values of (i,s) is (1,1). so, during the first iteration, initially, i will be incremented to 2, and then i will be added to s, so 2+1 = 3. hence, s becomes 3.

brilliant.org/wiki/sum-of-n-n2-or-n3/

+Subhash k start from i=1; not from i=0 as anything multiply by 0 is 0 so the value of i is not incremented.

I guess it is same, As you have written O(n) only which is same to big O of n.

you said you'll contact me ...i gave my number also in the mail...please call sir ...i'm desperate to take your course ...but before that i want to clarify some doubts regarding taking the course.

j isnt 1 yo n. its 1 to i.

👍👍👍👍

i try my best but it seems difficult for me

n(n+1)/2 = n^2 + n / 2 = n^2 = O(n^2)

Yes

In 19:52 time