Data Structure and Algorithm for Gate by Narasimha Karumanchi# Algorithm Introduction#

Question

Find the complexity of below pseudocode.

temp = 1

repeat

             for i=1 to n

                          temp=temp +1;

             n=n/2;

until n<= 1

Comments

n is not constant while iteration, right?

i mean by seeing repeat, we can just say log n, but how can you multiply by n due to n is also changing ?

---

No you are getting it wrong,initially when have n,in first iteration of repeat, the for loop is executed n times ,now n is getting divided by 2 so. we getn= n/2 ,so now in second iteration ,although for loop executed n times but n has changed ,same for next iterations it happens  ,hence the whole function is called again and again each time by  n/2 so it is behaving like recurrence

---

Okay...i got it...thanks for explanation

Answer 1

So, will it be nlogn or logn? I usually get confused in these two. If you know any trick, please let me know