871 views

3 Answers

1 votes
1 votes
$T(n) = T\left(\frac{n}{\lg n}\right) + 1$

$= T\left(\frac{n}{\lg n \lg (n/ \lg n)}\right) + 2$ (Going 1 level into recursion)

$= T\left(\frac{n}{ \lg ^2 n - \lg n \lg \lg n}\right) + 2$

$\dots$

Since the second term $(\lg n \lg \lg n)$ is asymptotically lower than $\lg^2 n$, we can ignore it and assume that the recurrence stops when the denominator is half of the numerator (when we get T(2)) which happens after $k$ steps and since the complexity at each step is 1, the total complexity will be $k$.

$\lg^k n = n/2$

$\lg n = (n/2)^{1/k}$

$\lg \lg n = (1/k) (\lg n -1)$

$k = (\lg n -1 )/\lg \lg n$

So, time complexity = $\Theta \left(\frac{\lg n}{\lg \lg n}\right)$
0 votes
0 votes
If i replace logn by root (n) then equation will be T(n) = T(root n) which is nothing but log log(n).

So final complexity O(log logn) < T(n) < n
0 votes
0 votes
It will be O(log n).In binary search you divide the entire array into 2 halves each time.In that case it would be O(log n) with base 2.in case you divide in 3 halves the base will become 3 in logarithm.But the base does not matter that much.It actually differs only by a constant.

Related questions

0 votes
0 votes
4 answers
1
1 votes
1 votes
2 answers
2
5 votes
5 votes
1 answer
3
0 votes
0 votes
2 answers
4
radha gogia asked Jul 7, 2018
1,547 views
foo(int n) { for(int i=0 ; i<n ;i++) for(int j=i ; j<=i*i ;j++) if(j%i==0) { for(int k=0;k<j;k++) printf("hii"); } } How to proceed here for analyzing the time complexity...