0 votes 0 votes What is the time & space complexity of this algorithm? Main() { for(i=n; i>10; i=i^1/4) { for(j=201; j<n^3; j=j+400) { for(k=47; k<=n^84; k=k*108) { k=k^61; } } } } Algorithms algorithms time-complexity space-complexity self-doubt + – Nisha Bharti asked Sep 26, 2022 • retagged Sep 26, 2022 by Shubham Sharma 2 Nisha Bharti 738 views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
1 votes 1 votes Ans Nisha Bharti answered Sep 26, 2022 Nisha Bharti comment Share Follow See all 4 Comments See all 4 4 Comments reply Pranavpurkar commented Sep 26, 2022 reply Follow Share Perfect👍Nisha Bhartican you explain this (47)^61^k.I got till (47)^61 but how k. just confused. 1 votes 1 votes Pranavpurkar commented Sep 26, 2022 reply Follow Share Nisha Bharti ohhh .. i think it would be better to take some different variable there. I got confused between variable k and that k :) 0 votes 0 votes Nisha Bharti commented Sep 26, 2022 reply Follow Share @Pranavpurkar if you know hindi then see k^61 yha k ka value 47 dia hua h that is called initialization now k^61 ye bar bar repeat hoga due to loop to kitna bar power 61 repeat hoga whi value dega k...isi lie 61^k lie h hum. aur whi value nikale h that is called complexity(looping). 0 votes 0 votes Pranavpurkar commented Sep 26, 2022 reply Follow Share Nisha Bharti YES i got that! 1 votes 1 votes Please log in or register to add a comment.
0 votes 0 votes I m getting time complexity = O(n^3*logn*loglogn) and space complexity = O(1) Pranavpurkar answered Sep 26, 2022 Pranavpurkar comment Share Follow See all 4 Comments See all 4 4 Comments reply Nisha Bharti commented Sep 26, 2022 reply Follow Share please explain in details with base & power. 0 votes 0 votes Pranavpurkar commented Sep 26, 2022 reply Follow Share .Nisha Bharti I mistakenly assumed the constraint in the last loop as k<=n^84 is it k or j? 0 votes 0 votes Nisha Bharti commented Sep 26, 2022 reply Follow Share sorry it is k @Pranavpurkar 0 votes 0 votes Pranavpurkar commented Sep 26, 2022 reply Follow Share Yup I have shared my approach! 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes This is my approach! EDIT: This answer has mistakes :( Pranavpurkar answered Sep 26, 2022 • edited Sep 26, 2022 by Pranavpurkar Pranavpurkar comment Share Follow See all 9 Comments See all 9 9 Comments reply Nisha Bharti commented Sep 26, 2022 reply Follow Share @Pranavpurkar Extraa marks for good handwriting💯 but ans is O[log base 61 log n^84 base 47 * n^3/400 * log base 4 log base 10 n] 0 votes 0 votes Pranavpurkar commented Sep 26, 2022 reply Follow Share 😅thanks Nisha Bharti is any explanation provided? 0 votes 0 votes Pranavpurkar commented Sep 26, 2022 reply Follow Share Nisha Bharti got my mistake here in the first loop it should not be ¼ it is only 4 (it is my mistake) and in the second loop it is divided by 400 (even i dont knw why i written 100 there) :( but according to me the last loop running time will be log(n^84) base 108 how u got loglogn? 0 votes 0 votes Pranavpurkar commented Sep 26, 2022 reply Follow Share Nisha Bharti I think i got it but stlll have some problems in the last loop here what is the significance of k = k*108 doesn’t it give a T.C = O(log(n^84) base 108) ? 0 votes 0 votes Nisha Bharti commented Sep 26, 2022 i edited by Nisha Bharti Sep 26, 2022 reply Follow Share @Pranavpurkar Actualy i forgot this.this question is from reddy sir lecturesrevision 0 so everything is 0 now. 0 votes 0 votes Nisha Bharti commented Sep 26, 2022 reply Follow Share @Pranavpurkar due to highier priority of power that is 61 means k^61 have more priority as compare to k*108 means k^61 increase fast as compare to k*108 that will be reason. 1 votes 1 votes Nisha Bharti commented Sep 26, 2022 reply Follow Share so we have to neglect k*108 0 votes 0 votes Pranavpurkar commented Sep 26, 2022 reply Follow Share Nisha Bhartiohhh!! got it.yes it seems correct reason. 0 votes 0 votes Pranavpurkar commented Sep 26, 2022 reply Follow Share Nisha Bharti this question was really good :) 1 votes 1 votes Please log in or register to add a comment.