Skip to main content
Computer Science

Return to Question

edited body
Source Link
V K
V K
  • 205
  • 2
  • 5

I am trying to solve the 4.6-2 question in CLRS book which is

$T(n)= aT(n/b) + \Theta(n^{\log_ba}\lg^{k}n)$

While solving the above equation I reach the following point:

  1. $T(n)= n^{\log_ba} + n^{\log_ba}\left( \sum_{j=0}^{\log_bn - 1}\lg^k(n/b^i)\right) $$T(n)= n^{\log_ba} + n^{\log_ba}\left( \sum_{j=0}^{\log_bn - 1}\lg^k(n/b^j)\right) $

when I searched online, I saw people have solved this as below:

  1. $T(n)= n^{\log_ba} + n^{\log_ba}\left( \sum_{j=0}^{\log_bn - 1}\lg^k(n)- \lg^k(b^i)\right) $$T(n)= n^{\log_ba} + n^{\log_ba}\left( \sum_{j=0}^{\log_bn - 1}\lg^k(n)- \lg^k(b^j)\right) $
  2. $T(n)= n^{\log_ba} + n^{\log_ba}\left( \sum_{j=0}^{\log_bn - 1}\lg^k(n)- o(\lg^k(n))\right) $
  3. $T(n)= n^{\log_ba} + n^{\log_ba}( \log_bn \cdot \lg^k(n)+ \log_bn \cdot o(\lg^k(n))) $
  4. $T(n)= n^{\log_ba} + \Theta(n^{\log_ba}\lg^{k+1}(n)) $

I did not understand the following points:

  • $ \lg^kn/b^i = (\lg n - \lg b^i)^k $, then how in equation 2, we can have power k on individual logs?
  • In equation 4, after calculating the summation, how did the subtraction between logs turn to sum?
  • There is a small o in equation 4, then how can we write theta in equation 5.

I am trying to solve the 4.6-2 question in CLRS book which is

$T(n)= aT(n/b) + \Theta(n^{\log_ba}\lg^{k}n)$

While solving the above equation I reach the following point:

  1. $T(n)= n^{\log_ba} + n^{\log_ba}\left( \sum_{j=0}^{\log_bn - 1}\lg^k(n/b^i)\right) $

when I searched online, I saw people have solved this as below:

  1. $T(n)= n^{\log_ba} + n^{\log_ba}\left( \sum_{j=0}^{\log_bn - 1}\lg^k(n)- \lg^k(b^i)\right) $
  2. $T(n)= n^{\log_ba} + n^{\log_ba}\left( \sum_{j=0}^{\log_bn - 1}\lg^k(n)- o(\lg^k(n))\right) $
  3. $T(n)= n^{\log_ba} + n^{\log_ba}( \log_bn \cdot \lg^k(n)+ \log_bn \cdot o(\lg^k(n))) $
  4. $T(n)= n^{\log_ba} + \Theta(n^{\log_ba}\lg^{k+1}(n)) $

I did not understand the following points:

  • $ \lg^kn/b^i = (\lg n - \lg b^i)^k $, then how in equation 2, we can have power k on individual logs?
  • In equation 4, after calculating the summation, how did the subtraction between logs turn to sum?
  • There is a small o in equation 4, then how can we write theta in equation 5.

I am trying to solve the 4.6-2 question in CLRS book which is

$T(n)= aT(n/b) + \Theta(n^{\log_ba}\lg^{k}n)$

While solving the above equation I reach the following point:

  1. $T(n)= n^{\log_ba} + n^{\log_ba}\left( \sum_{j=0}^{\log_bn - 1}\lg^k(n/b^j)\right) $

when I searched online, I saw people have solved this as below:

  1. $T(n)= n^{\log_ba} + n^{\log_ba}\left( \sum_{j=0}^{\log_bn - 1}\lg^k(n)- \lg^k(b^j)\right) $
  2. $T(n)= n^{\log_ba} + n^{\log_ba}\left( \sum_{j=0}^{\log_bn - 1}\lg^k(n)- o(\lg^k(n))\right) $
  3. $T(n)= n^{\log_ba} + n^{\log_ba}( \log_bn \cdot \lg^k(n)+ \log_bn \cdot o(\lg^k(n))) $
  4. $T(n)= n^{\log_ba} + \Theta(n^{\log_ba}\lg^{k+1}(n)) $

I did not understand the following points:

  • $ \lg^kn/b^i = (\lg n - \lg b^i)^k $, then how in equation 2, we can have power k on individual logs?
  • In equation 4, after calculating the summation, how did the subtraction between logs turn to sum?
  • There is a small o in equation 4, then how can we write theta in equation 5.
added 48 characters in body
Source Link
Yuval Filmus
Yuval Filmus
  • 279.1k
  • 27
  • 316
  • 512

I am trying to solve the 4.6-2 question in CLRS book which is

$T(n)= aT(n/b) + \Theta(n^{\log_ba}lg^{k}n)$$T(n)= aT(n/b) + \Theta(n^{\log_ba}\lg^{k}n)$

While solving the above equation I reach the following point:

  1. $T(n)= n^{\log_ba} + n^{\log_ba}( \sum_{j=0}^{\log_bn - 1}\lg^k(n/b^i)) $$T(n)= n^{\log_ba} + n^{\log_ba}\left( \sum_{j=0}^{\log_bn - 1}\lg^k(n/b^i)\right) $

when I searched online, I saw people have solved this as below:

  1. $T(n)= n^{\log_ba} + n^{\log_ba}( \sum_{j=0}^{\log_bn - 1}\lg^k(n)- lg^k(b^i)) $$T(n)= n^{\log_ba} + n^{\log_ba}\left( \sum_{j=0}^{\log_bn - 1}\lg^k(n)- \lg^k(b^i)\right) $
  2. $T(n)= n^{\log_ba} + n^{\log_ba}( \sum_{j=0}^{\log_bn - 1}\lg^k(n)- o(lg^k(n))) $$T(n)= n^{\log_ba} + n^{\log_ba}\left( \sum_{j=0}^{\log_bn - 1}\lg^k(n)- o(\lg^k(n))\right) $
  3. $T(n)= n^{\log_ba} + n^{\log_ba}( log_bn.lg^k(n)+ log_bn.o(lg^k(n))) $$T(n)= n^{\log_ba} + n^{\log_ba}( \log_bn \cdot \lg^k(n)+ \log_bn \cdot o(\lg^k(n))) $
  4. $T(n)= n^{\log_ba} + \Theta(n^{\log_ba}lg^{k+1}(n)) $$T(n)= n^{\log_ba} + \Theta(n^{\log_ba}\lg^{k+1}(n)) $

I did not understand the following points:

  • $ \lg^kn/b^i = (lgn - lgb^i)^k $$ \lg^kn/b^i = (\lg n - \lg b^i)^k $,then then how in equation 2, we can have power k on individual logs?
  • In equation 4, after calculating the summisionsummation, how did the subtraction between logs turn to sum?
  • There is a small o in equation 4, then how can we write theta in equation 5.

I am trying to solve the 4.6-2 question in CLRS book which is

$T(n)= aT(n/b) + \Theta(n^{\log_ba}lg^{k}n)$

While solving the above equation I reach the following point:

  1. $T(n)= n^{\log_ba} + n^{\log_ba}( \sum_{j=0}^{\log_bn - 1}\lg^k(n/b^i)) $

when I searched online, I saw people have solved this as below:

  1. $T(n)= n^{\log_ba} + n^{\log_ba}( \sum_{j=0}^{\log_bn - 1}\lg^k(n)- lg^k(b^i)) $
  2. $T(n)= n^{\log_ba} + n^{\log_ba}( \sum_{j=0}^{\log_bn - 1}\lg^k(n)- o(lg^k(n))) $
  3. $T(n)= n^{\log_ba} + n^{\log_ba}( log_bn.lg^k(n)+ log_bn.o(lg^k(n))) $
  4. $T(n)= n^{\log_ba} + \Theta(n^{\log_ba}lg^{k+1}(n)) $

I did not understand the following points:

  • $ \lg^kn/b^i = (lgn - lgb^i)^k $,then how in equation 2, we can have power k on individual logs?
  • In equation 4, after calculating the summision, how did the subtraction between logs turn to sum?
  • There is a small o in equation 4, then how can we write theta in equation 5.

I am trying to solve the 4.6-2 question in CLRS book which is

$T(n)= aT(n/b) + \Theta(n^{\log_ba}\lg^{k}n)$

While solving the above equation I reach the following point:

  1. $T(n)= n^{\log_ba} + n^{\log_ba}\left( \sum_{j=0}^{\log_bn - 1}\lg^k(n/b^i)\right) $

when I searched online, I saw people have solved this as below:

  1. $T(n)= n^{\log_ba} + n^{\log_ba}\left( \sum_{j=0}^{\log_bn - 1}\lg^k(n)- \lg^k(b^i)\right) $
  2. $T(n)= n^{\log_ba} + n^{\log_ba}\left( \sum_{j=0}^{\log_bn - 1}\lg^k(n)- o(\lg^k(n))\right) $
  3. $T(n)= n^{\log_ba} + n^{\log_ba}( \log_bn \cdot \lg^k(n)+ \log_bn \cdot o(\lg^k(n))) $
  4. $T(n)= n^{\log_ba} + \Theta(n^{\log_ba}\lg^{k+1}(n)) $

I did not understand the following points:

  • $ \lg^kn/b^i = (\lg n - \lg b^i)^k $, then how in equation 2, we can have power k on individual logs?
  • In equation 4, after calculating the summation, how did the subtraction between logs turn to sum?
  • There is a small o in equation 4, then how can we write theta in equation 5.
Source Link
V K
V K
  • 205
  • 2
  • 5

Solution of CLRS question 4.6-2

I am trying to solve the 4.6-2 question in CLRS book which is

$T(n)= aT(n/b) + \Theta(n^{\log_ba}lg^{k}n)$

While solving the above equation I reach the following point:

  1. $T(n)= n^{\log_ba} + n^{\log_ba}( \sum_{j=0}^{\log_bn - 1}\lg^k(n/b^i)) $

when I searched online, I saw people have solved this as below:

  1. $T(n)= n^{\log_ba} + n^{\log_ba}( \sum_{j=0}^{\log_bn - 1}\lg^k(n)- lg^k(b^i)) $
  2. $T(n)= n^{\log_ba} + n^{\log_ba}( \sum_{j=0}^{\log_bn - 1}\lg^k(n)- o(lg^k(n))) $
  3. $T(n)= n^{\log_ba} + n^{\log_ba}( log_bn.lg^k(n)+ log_bn.o(lg^k(n))) $
  4. $T(n)= n^{\log_ba} + \Theta(n^{\log_ba}lg^{k+1}(n)) $

I did not understand the following points:

  • $ \lg^kn/b^i = (lgn - lgb^i)^k $,then how in equation 2, we can have power k on individual logs?
  • In equation 4, after calculating the summision, how did the subtraction between logs turn to sum?
  • There is a small o in equation 4, then how can we write theta in equation 5.