Q14- How to calculate the complexity of both together?

#1

Sir
In QUESTION 14, I understood how to find the complexity of each loop ie. logN, but after combining them the final answer is loglogN. Can you please help me in this as how we are combining them and how to do it for any other question?
Thankyou
Tushar Joshi

#2

and also sir in Q14, wont the inner loop be infinite loop, I mean taking continuous root of a number wont go less than 1 I guess so condition is always true?

#3

@tushar725 can you copy paste the question here or send a screenshot, i am not able to see the quiz

#4

Find the time complexity of the given code.

void pat(){

for (int i = 2; i <=n; i = pow(i, c)) {
//Print statement - O(1) operation
}

//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
}
}
O(N LogN)

O(N^3)

O(N^2)

LogLog N

#5

@tushar725 i is of int type so after a while, fun(i) will return something like 1.4 or anything which will be rounded off to 1, the condition will become false and the loop will break. So no infinite loops.

1 Like
#6

and mam the combining part? how to do that?

#7

@tushar725 see the first answer here https://stackoverflow.com/questions/16472012/what-would-cause-an-algorithm-to-have-olog-log-n-complexity

1 Like
#8

so mam the first loop has complexity logN and second has loglogN, so why the combined will have the smaller complexity or there is any other reason? or the first loop’s complexity isn’t logN?
I’ll attach the solution provided by CODING BLOCKS.

Q14) Find complexity of the following
void pat(){
//executes log (input size) times
for (int i = 2; i <=n; i = pow(i, c)) {
System.out.print("")
}
//Here fun is sqrt or cuberoot or any other constant root
//executes log n times
for (int i = n; i > 1; i = fun(i)) {
System.out.print("")
}
}
a) O(N LogN)
b) O(N^3)
c) O(N^2)
d) LogLog N
Answer is d) LogLogN
Explanation: Explained in comments in code.

#9

@tushar725 https://www.geeksforgeeks.org/time-complexity-loop-loop-variable-expands-shrinks-exponentially/ this should answer all your questions

1 Like
#10

@tushar725 the 5th point here https://www.geeksforgeeks.org/analysis-of-algorithms-set-4-analysis-of-loops/

1 Like
#11

oh got it mam thankyou very much.

#12

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.

1 Like