#Algorithm Help Solving Recurrence of Select Algorithm with guaranteed Linear time O(n)

Question

Solution to the Recurrence equation $T(n) = T(n/5)+T(7n/10)+O(n)$ is

Answer 1

....

Comments

@ ankitgupta.1729  Bhai, maths mein kamzoor hai. Zara yeh wala step bta dijye - jisme (9/10)²n aaya hai?

Apne ko tisra level recursion tree ka samaj nai aa raha. Aapne problem ko kaise divide kar rahe ho bhai?

See this image - https://imgur.com/a/lqn4a

---

@Iarnav , bhai kuch nhi bas har level pe sum kar diya hai..  kyonki hume har level ke liye bhi total cost nikalni hai .. ..

0^th level :-  n

1^st level :- n/5 + (7n/10) = (2n/10) + (7n/10) = (9n/10)

2^nd level :- (n/5²) + (7/10)*(n/5) + (7/10)*(n/5) + (7/10)²n = (4*n/4*5²) + (7/10)*(2*n/2*5) +  (7/10)*(2*n/2*5) + (7/10)²n = (4n /100) + (14n/100) + (14n/100) + (49n/100) = 81n/100 = (9/10)² n...

bhai aise hi 3rd level ke liye sum karoge to (9/10)³*n. milega...to yha pe hume ek pattern milega har level ke liye jo GP series hogi humari...phir last me total sum kar denge...

yhe pe problem ko recursion equation

T(n/5)+T(7n/10)

ko dekh ke divide karna hai..

sabse pahle humare paas "n" hai..to 1st level ke liye , n ko replace kar do (n/5) se aur left me rakh do isko..aur phir n ko replace kar do 7n/10 aur isko right me rakh do..

2^nd level :- 1st level pe humare paas n/5 aur  7n/10 aaya tha..to n/5 ko pahle break kar lo..so , n/5 me 'n' ki jagah pe n/5 daaloge to n/5² mil jaayega to isko left me daal do  n/5 ke..phir n/5 me 'n' ki jagah pe   7n/10 rakhoge to (7n/10)/5 = (7n/(10*5)) milega.. to isko right me daal denge..isi tarah har node ki value ko dekhiye aur 'n' ko n/5 se replace karke left me rakh  dijiye aur n ko 7n/10 se replace karke right me rakh dijiye...

bhai if u r not getting anything then please ask again ..I will again explain...

---

@ankitgupta.1729 Bhai, pehle toh aap ho mahan, ek dum faad samjaya, toh uske liye much repsect and aapke charno mein parnam (literally touching your feet like you're a guru) and yes, you explained it very nicely in hindi. So, thank you! 

Now, abhi thode se doubt hai - 

1) Yeh jo (7/10)^k = 1 yeh K'th level see aaya hai na tree ke?

2) humne n =(10/7)k tak find kar liya and ab iske baad apne ko log lena padega toh meine log liya toh woh yeh aa raha hai - 

logn = k.log(10/7) toh apan ko yeh samaj nai aa raha ke iske baad kaise k = log (10/7)ⁿ kaise bangaya? Bhai, app koi property lagaye kya log ke?

Bhai, yeh jo k = log (10/7)ⁿ likhe ho, yeh (10/7) base toh nai hai log ka and n toh sirf saath mein hai jaise log(_10/7)n yeh (10/7) paaron mein hai.

---

@Iarnav ,

1) Yeh jo (7/10)^k = 1 yeh K'th level see aaya hai na tree ke?

yes..0th level :-(7/10)⁰n ,1st level :- (7/10)¹n ,2nd level :- (7/10)²n , 3rd level :- (7/10)³n ..so, kth level:(7/10)^kn

it is the slowest deceasing term on every level..so height of the tree will be decided by it.

2) yeh jo k = log (10/7)ⁿ likhe ho, yeh (10/7) base toh nai hai log ka and n toh sirf saath mein hai jaise log(_10/7)n

yes..base is 10/7...here , (7/10)^k n = 1 ...(7^k /10^k)*n = 1..so , n = 10^k / 7^k ...n = (10/7)^k ...Now , take log both sides with base  10/7...So , it becomes log_10/7n = k*log_10/7 (10/7)..since log_aa= 1..So,  log_10/7n = k..

I have used one log property also..a^log_bc= c^log_ba ..So, (9/10)^log_10/7n = n^{log_10/7(9/10)} = n^{log_e(9/10)/log_e(10/7)} ..Since log_cb = log_ab / log_ac ..here , I have taken 'a' as 'e'..I have written natural log as ln e..It means log base e...

If u have any doubt then please ask..

Answer 2

I think you want to ask time complexity of recurrence relation.

It is easy to solve by recurrence tree.

1st level:       O(n)

2nd level =  O( 7n/10 + n/5) = O(9n/10)

3rd level  =  O( 7n/50 + 49/100 + 7n/50 + n/25)   =  O (81n/100)  

...

................. and so on.

T (n)   =  O ( n + 9n/10 + 81n/100 + ..................)  ( infinite G.P sum)

          = O(10n) = O(n)

Comments

I  agree with you. Is there any reference from where i really clear my doubt that recurrence tree that every recurrence relation has anchor condition.

Moreover, Recurrence tree is not proof of any asymptotic notion. We get little bit intuition  about complexity of algorithm.

---

Recurrence tree is not proof of any asymptotic notion. We get little bit intuition  about complexity of algorithm.

If you are very careful when drawing out a recursion tree and summing the costs ,however you can use a Recursion Tree as a direct proof of a solution to a recurrence.

Source :- Cormen

Is there any reference from where i really clear my doubt that recurrence tree that every recurrence relation has anchor condition.

https://en.wikipedia.org/wiki/Recurrence_relation

---

When you write a recurrence relation you must write two equations: one for the general case and one for the base case. These correspond to the recursive function to which the recurrence applies. The base case is often an O(1) operation, though it can be otherwise. In some recurrence relations the base case involves input of size one, so we wrote T(1) = O(1). However, there are cases when the bse case has size zero. In such cases the base could would be T(0) = O(1).

Ref :- https://users.cs.duke.edu/~ola/ap/recurrence.html