in Algorithms
585 views
4 votes
4 votes

For the following program fragment, the running time is given by

Procedure A(n) 
{
    if(n <= 2) 
        return 1; 
    else return A(log (n)); 
}
  1. $\Theta(\log \log n)$
  2. $\Theta(\log \sqrt n)$
  3. $\Theta(\log^* n)$
  4. $\Theta(\sqrt n)$
in Algorithms
by
585 views

2 Comments

not able to how to approach please help me
0
0
edited by

can someone plz explain option C

what is * here??? 

0
0

2 Answers

6 votes
6 votes
Best answer

$T(n) = T(\log n) + 1$

Solution to this recurrence is : no of times logrithmic function applied on $n$ in order to get base condition, which is nothing but $\log^* n$.

Complexity $=\Theta (\log ^*n)$

selected by

16 Comments

sir, if we run this algo for n= 22^10.

Then I think, It will run like - 

T( 22^10.) 

T( 210)

T( log 10 = 3.xy)

T ( log (3.xy) )

return ... right ..

Here TC is approx - 5 recursive function calls.


And log n for n =22^10. will result TC = 210  fn calls  .. which is not close to actual ans  right  ??


if it was- 

  1. Procedure A(n)
  2. {
  3. if(n <= 2)
  4. return 1;
  5. else return A(n/2);
  6. }

then ans should be  TC = Log n .... right ??

0
0
edited by
we can write like this:

T(n) = T(logn) + 1

T(logn) = T(loglogn) +1

so,

T(n) = T(loglogn) + 1 +1

        =T(log^kn) +k

log^kn is loglog.............logn k times

hence answer is (C)
3
3
@vijay It must be done recursively- you are taking log only for one level.
1
1
@cse23

log^kn =2

You already got answer here. Even if you don't know what is $\log^*$, all other options can be eliminated here. You cannot apply any simplication after this as you had done as

$\log^k n = \underbrace{\log \log \dots \log}_{k \text{ times}} n \neq \frac{\log k}{\log n}.$
1
1
thanks arjun sir..:) even I was bit confuse at that step
1
1
got it now .. thanks... could not recognize * .. :P
2
2
edited by
Good Question
0
0
sir i have same dought as @vijaycs and from your comment i can not get till now can you please further explain in detail. and what is meaning fo * in logrithm
0
0
@Manoj. Take some large value of 'n' and calculate which option will be closest to the answer.
0
0
log^2(n)= logn * logn     or    log(logn)???/

can any one expain? I am getting confused.
0
0
log^2(n)=log(logn)

(logn)^2=logn*logn
0
0
but sir we r doing it by option elimination which is correct but to solve further like how to calculate k in recurrence relation like in other tc quedtions here k is not confirm it is depending on input n
0
0
0
0
no it is very different u can check it by taking a simple example like take a number apply 2 times log and in second way take 1 time log and multiply it 2 times . u can see large differnce so

(logn)^2 not eql to log^2n
0
0

Applying Log 2 times will be Log(Log(x)) that is different from Log(x)* Log(x). but still Log2x = Log(x) * Log(x).

Its just same as Sin2(x)= Sin(x)*Sin(x)

0
0
sin^2x is not equal to sinx * sinx . just remember ur trignometry class if it is that much simple then why we apply cos2x formulae to calculate it just multipy two times and get result if u do this all trignometric identity gone wrong.
0
0
1 vote
1 vote

Let's take some values of n.

Clearly, the recurrence is  $T(n)=T(logn)+1$

I'll take it as $T(n)=T\left \lceil (logn) \right \rceil+1$ because $logn = O\left \lceil (logn) \right \rceil$


n = $1024$

$1024\rightarrow 10\rightarrow 4\rightarrow 2$

3 recursive calls.

So, for 1024, it is $O(loglogn)$


n = $2^{2048}$

$2^{2048}\rightarrow 2048\rightarrow 12\rightarrow 4\rightarrow 2$

4 recursive calls.

So, for $2^{2048}$ it is $O(logloglogn)$


n = $2^{2^{2^{2048}}}$

$2^{2^{2^{2048}}}\rightarrow $ $2^{2^{2048}}\rightarrow $ $2^{2048}\rightarrow 2048\rightarrow 12\rightarrow 4\rightarrow 2$

6 recursive calls.

So, for $2^{2^{2^{2048}}}$ it is $O(loglogloglogn)$


 

It is evident that number of logs is dependent upon how big the input value is. So, it would be Option C

Answer:

Related questions