0 votes 0 votes int x = 0; int f(n) { if(n == 1) return; else { x += 4*A(n/2) + n^2 return X; } What will be the recurrence relation and time complexity ?? jatin khachane 1 asked Jul 22, 2018 jatin khachane 1 429 views answer comment Share Follow See all 7 Comments See all 7 7 Comments reply MiNiPanda commented Jul 22, 2018 reply Follow Share Is it O(logn) ? 0 votes 0 votes Shubham Shukla 6 commented Jul 22, 2018 reply Follow Share recurrence relation T(n)=T(n/2)+O(1) time complexity=O(log n) 1 votes 1 votes jatin khachane 1 commented Jul 22, 2018 reply Follow Share int rec(int n) { If(n==1) return; else { return(rec(n-1) + rec(n-1)); } } Here equation will be : T(n)= T(n-1) + T(n-1) + 1 Here individual times for rec(n-1) are taken unlike in above example where 4*A(n/2) where Only T(n/2) is taken becoz after that its just multiplication with constant 4 . If it is like x+=A(n/2)+A(n/2)+n^2 Equ : T(n) = 2T(n/2) +1 Am i right ..sorry for so lengthy question ☺ 1 votes 1 votes Shubham Shukla 6 commented Jul 22, 2018 reply Follow Share yes absolutely right the point which is hidden in qsn you have got it correctly..the things you have mentioned only need to be taken care off..! 0 votes 0 votes jatin khachane 1 commented Jul 22, 2018 reply Follow Share Means writing 2*A(n/2) and A(n/2)+A(n/2) in code will cause different time complexities ??..how beautiful it is 0 votes 0 votes Shaik Masthan commented Jul 22, 2018 reply Follow Share Yes.... But values return by them are equal 1 votes 1 votes Shubham Shukla 6 commented Jul 22, 2018 reply Follow Share time complexity recurrence relation would be different...but if you need to calculate values than their recurrence relation would be same..! For value both will have=2T(n/2)+O(1) and for complexities 1st will have T(n)=T(n/2)+O(1) and 2nd eqn will have T(n)=2T(n/2)+O(1) 0 votes 0 votes Please log in or register to add a comment.