//Here fun is sqrt or cuberoot or any other constant root
for (int i = n; i > 1; i = fun(i)) {
//Print statement - O(1) operation
}
bhaiya iska time complexity kaise calculate kare, soiution send kar dijiye
Time compxexity
lg (n!) = ……………… iska bhi time complexity ka solution send kar dijiye
hi @ritikbunty2511_729d0258992e0982,
first iteration i is 2
in second iteration i will be 2^k
in third iteration i will be (2^k)^k = 2^(k^2)
in fourth iteration i will be 2^(k^3)
in i+1th iteration i will be 2^(k^(i))
for loop to stop
2^(k^(i) ) > n
take log base 2 both side
k^(i) > log2(n)
take log base k both side
i > log k log2(n)
so this option is correct->LogLog N
bhaiya is question mai 2 loop hai upper loop ka maine bhi solve kar liya hai jo loop maine send kiye hai uska complexity ke solution send kijiye
@ritikbunty2511_729d0258992e0982 uska complexity utna hi hai jitna upar k loop ka as such us loop me kuch ho ni raha na wo bs fun ko call kr raha and i ki value fun hi change kr raha
but how can i calculate the complexity of lower loop ??
@ritikbunty2511_729d0258992e0982 keep adding the no of times its running and that is here controlled by fun so the no of times fun gets called is your ans
ye sab hame bhi pata hai, but the thing is i am not able to find number of times the loop runs, yehi mai bol rahe hu ke iska calculation send kar dijiye
hi @ritikbunty2511_729d0258992e0982,
In second case i ki values aise change hogi
n
n1/k
(n1/k)1/k = n1/k2
n1/k3, …, n1/klogk(log(n))
to totally logk(log(n)) iterations ho jayenge
and time complexity is O(log(log(n))).
@ritikbunty2511_729d0258992e0982,
log(1 .2 .3.4.5.6…n) = log 1 + log 2 + log 3. … logn
which is less than
log n + log n + log n …log n
now this log n factor is written n times
n * log n
hence the time complexity in worst case is n * log n