You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
I think there is a major error in the solution for the exercise 4.3.6. We pass from $$T(n) = c(n+34-2a)lg(n+34-2a)-c(n+34-2a)+n$$ to $$T(n) <= c(n+34-2a)lg(n+34-2a)$$ assuming c > 1 but we then pass from this to $$T(n) <= c(n-a)lg(n-a)$$ assuming a >= 34 but if a >= 34 then the previous step is not valid, if we have a >= 34 and c > 1 then we do have $c(n+34-2a) = c*n$ so we do not have $-c(n+34-2a)+n < 0$ so we can't pass from $$T(n) = c(n+34-2a)lg(n+34-2a)-c(n+34-2a)+n$$ to $$T(n) <= c(n+34-2a)lg(n+34-2a)$$.
The text was updated successfully, but these errors were encountered:
RyanTalbi
changed the title
Exercise 4.3.6
Is solution to exercise 4.3.6 wrong ?
Aug 8, 2022
I think there is a major error in the solution for the exercise 4.3.6. We pass from$$T(n) = c(n+34-2a)lg(n+34-2a)-c(n+34-2a)+n$$ to $$T(n) <= c(n+34-2a)lg(n+34-2a)$$ assuming c > 1 but we then pass from this to $$T(n) <= c(n-a)lg(n-a)$$ assuming a >= 34 but if a >= 34 then the previous step is not valid, if we have a >= 34 and c > 1 then we do have $c(n+34-2a) = c*n$ so we do not have $-c(n+34-2a)+n < 0$ so we can't pass from $$T(n) = c(n+34-2a)lg(n+34-2a)-c(n+34-2a)+n$$ to $$T(n) <= c(n+34-2a)lg(n+34-2a)$$ .
The text was updated successfully, but these errors were encountered: