in Algorithms
873 views
2 votes
2 votes

// 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? 

Source: http://www.geeksforgeeks.org/time-complexity-loop-loop-variable-expands-shrinks-exponentially/

in Algorithms
873 views

1 Answer

2 votes
2 votes

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)

Related questions