873 views
 // func() is any constant root function for (int i = n; i > 0; 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)))."

Can someone explain the above statement? How do we calculate that there are logk(log(n)) iterations?

## 1 Answer

func() is given as root function. So, we write it as  n, n1/k, n1/k2, n1/k3, …, n1/kp

Where we assume that n1/k is the last term that is >0 (lets take it to be = e) according to the loop.(e = smallest positive root) Now

n1/k = e

taking log on both sides (1/k)loge(n) = loge(e)

(1/k)loge(n) =  1

log(n) = kp

again taking log on both the sides log(loge(n)) = p log(k)

therefore p =  [log(loge(n)) ]  /  [log(k)]

we know that [log (a)] / [log(b)] = logba

therfore p = logk(loge(n)

by

1 vote
0 answers
1
0 votes
0 answers
2
5 votes
1 answer
3
1,978 views