Time Complexity of a loop is considered as O(Logn) if the loop variables is divided / multiplied by a constant amount.
loop 1 ----
for (int i = 1; i <=n; i *= c)
{
// some O(1) expressions
}
loop 2 -----
for (int i = n; i > 0; i /= c)
{
// some O(1) expressions
}
Time Complexity of a loop is considered as O(LogLogn) if the loop variables is reduced / increased exponentially by a constant amount.
Here c is a constant greater than 1
loop 3 ----
for (int i = 2; i <=n; i = pow(i, c))
{
// some O(1) expressions
}
loop 4 -----
////Here fun is sqrt or cuberoot or any other constant root
for (int i = n; i > 0; i = fun(i))
{
// some O(1) expressions
}
Can anyone explain me why it is by considering the number of times the inner loop executes in these loops?
If c=1 in loop 1 and loop 2 then it will run infinite times right but it is given as logarithimic time why?
how is it O(loglogN) in loop 3 and loop 4?
If c=1 in loop 1 and loop 2 then it will run infinite times right but it is given as logarithimic time why?
Yes you are right, if c = 1 then we will get infinite loops for both case 1 and case 2, so the condition "c is a[n integer] constant greater than 1" is also necessary for both case 1 and case 2 in order to get the O(log n) complexity.
For case 1, note that i takes values 1, c, c2, c3, ..., clogc(n), so there are in total log(n) many iterations, and for each iteration there is a constant amount of work to be done (i.e. O(1) amount of work), so the total amount of work done is log(n) * O(1) = O(log(n)).
Similarly for case 2, i takes values n, n / c, n / c2, n / c3, ..., , n / clogc(n), so there are in total log(n) many iterations and each iteration takes constant amount of time, so the total time complexity is O(log(n)).
For case 3, i takes values 2, 2c, (2c)c = 2c2, (2c2)c = 2c3, ..., 2clogc(log(n)). The last term has to be less than or equal to n, and we have 2clogc(log(n)) = 2log(n) = n, which justifies the value of our last term. So there are in total logc(log(n)) many iterations, and each takes a constant amount of time to run, therefore the total time complexity is O(log(log(n))).
Similarly for case 4, i takes values n, n1/c, (n1/c)1/c = n1/c2, n1/c3, ..., n1/clogc(log(n)), so there are in total logc(log(n)) iterations and each iteration takes time O(1), so the total time complexity is O(log(log(n))).
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments