# Time compxexity

//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

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 bheji hai na bhai tujhe calculation…

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