Solution explanation to Quiz questions 1,6,10,14
Space and Time Complexity
Find the time complexity of the given code. void pat(){ for (int i = 2; i <=n; i = pow(i, c)) { print("") } //Here fun is sqrt or cuberoot or any other constant root for (int i = n; i > 1; i = fun(i)) { print("") } }
Considering both statements one by one:
1st:
for (int i = 2; i <=n; i = pow(i, k))
{
// some O(1) expressions or statements
}
In this case, i takes values 2, 2k, (2k)k = 2k2, (2k2)k = 2k3, …, 2klogk(log(n)). The last term must be less than or equal to n, and we have 2klogk(log(n)) = 2log(n) = n, which completely agrees with the value of our last term. So there are in total logk(log(n)) many iterations, and each iteration takes a constant amount of time to run, therefore the total time complexity is O(log(log(n))).
2nd:
for (int i = n; i > 1; i = func(i))
{
// some O(1) expressions or statements
}
In this case, i takes values n, n1/k, (n1/k)1/k = n1/k2, n1/k3, …, n1/klogk(log(n)), so there are in total logk(log(n)) iterations and each iteration takes time O(1), so the total time complexity is O(log(log(n))).
So the time complexity here is O(log(log(n))).
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.