GO Classes Test Series 2024 | Mock GATE | Test 12 | Question: 54

Answer 1

Since asymptotic growth is asked, we can, without loss of generality, assume $n=2^k$. Now, solving, it is easy.

Comments

@Philosophical_Virus if you see the above Advanced Master Theorem Rule, you will realize that here this question falls in the a) of Case 2 as p = 1 which is greater than -1 and as a=b^k. 

therefore, instead of your k+1 = 2, i think it should be p+1 = 2 which gives O( log n/2 ) and NOT O (log ^2 (n/2))

@GO Classes can you kindly elaborate this question please🙏

---

@Swarnava Bose I think I have taken k inplace of p in my formula as power of log().

---

how does f(2n+1) helps here , we haven’t used it in our solution..what can we infer from it ?

@GO Classes @Sachin Mittal 1

Answer 2

Credit goes to @Dhruva

Another approach is to solve it by Master's Theorem as shown in the comments

Answer 3

Let’s compute the first few values of f(N) and see how it behaves -
 

For N=1, f(1) = 0 (Given)

Also, f(2N+1) = f(2N). = f(N) + log(N)

Substituting N =1, we get f(3) = f(2) = f(1) + log(1) = log(1) (Since f(1) = 0)

Similarly, substituting N=2, we get f(5) = f(4) = f(2) + log(2) = log2 (Since f(2) = 0)

N =3, f(7) = f(6) = f(3) + log3 = log3
N=4, f(9) = f(8) = f(4) + log(4) = log(2) + log(4) = log(8) 
N=5, f(11) = f(10) = f(5) + log(5) = log(2) + log(5) = log(10)
N=6, f(13) = f(12) = f(6) +log(6) = log(3) + log(6) = log(18)

[Notice from f(8) onwards, the function is sum of two logs]

N=7, f(15) = f(14) = f(7) + log(7) = log(3) + log(7) = log(21)
N=8, f(17) = f(16) = f(8) + log(8) = log(4) + log(8) = log(32)
N=9, f(19) = f(18) = f(9) + log(9) = log(4) + log(9) = log(36)
N=10, f(21) = f(20) = f(10) + log(10) = log(5) + log(10) = log(50)

and so on……

For large even N, this can be generalized as f(N) = f(N/2) + log(N/2)

For large odd N, this can be generalized as f(N) = f((N-1)/2) + log((N-1)/2)

So for large N, f(N) consists of two terms – f(N/2) and log(N/2)

Now f(N/2) will again be a sum of f(N/4) and log(N/4)

Let’s see how many terms we get for different large values of N.

f(100) = log(50) + log(25) + log(12) + log(6) + log(3)

f(1000) = log(500) + log(250) + log(124) + log(62) + log(31) + log(15) + log(7) + log(3)

Therefore the dominating term is always log(N/2).

This implies that f(N) is O(log(N)).

EDIT – 

This is of the form log(N) + log(N/2) + log(N/4) + log(N/8)………….

This type of function has time complexity of O(log(n)²)

Source – https://stackoverflow.com/questions/44231116/is-complexity-ologn-logn-2-logn-4-logn-8-log2-olog

Comments

Apart from the Edit at the last, i think it is a wrong approach . You should edit the entire answer.

---

Yeah, could have substituted N=N/2 directly in the function and solved for f(N).