This question refers to my previous one.

The following repetition relationship is given: $ T (n) = aT (floor / floor) + f (n) $ from where $ a geq 1, b> 1 $ and $ f (n) = theta (n ^ { log_ba}) $, Then $ T (n) = n ^ { log_ba} + sum_ {j = 0} ^ { lfloor log_bn rfloor – 1} a ^ {j} f (n_j) = n ^ { log_ba} + g ( n) $, It should be proved $ g (n) = omega (n ^ { log_ba} logn) $,

It does not seem to be a difficult problem, as there is evidence of a similar (for the upper bound and a presence of the ceiling operation on recursive calls) in the *Introduction to the algorithms of Cormen, Leiserson, Rivest, Stein*, But I've found it harder to handle $ b = 2 $:

$ n_j = begin {cases}

n, & text {if j = 0} \

lfloor n_ {j-1} / b rfloor, & text {if j> 0}

end {cases} $

$ n_j geq n / b ^ {j} – sum_ {i = 0} ^ {j-1} 1 / b ^ {i} geq n / b ^ {j} – sum_ {i = 0} ^ { infty} 1 / b ^ {i} = n / b ^ {j} – b / (b-1) $

Under the condition there is such a constant $ c $ The

$ g (n) geq $

$ c sum_ {j = 0} ^ { lfloor log_bn rfloor – 1} a ^ {j} ( frac {n} {b ^ {j}} – frac {b} {b-1}) ^ {log_ba} = $

$ cn ^ {log_ba} sum_ {j = 0} ^ { lfloor log_b n rfloor – 1} (1- frac {b ^ {j}} {n} frac {b} {b-1} ) ^ {log_ba} geq $ //from where $ frac {b ^ {j}} {n} le 1 $

$ cn ^ {log_ba} sum_ {j = 0} ^ { lfloor log_b n rfloor – 1} (1- frac {b ^ { lfloor log_bn lfloor -1}} {n} frac {b } {b-1}) ^ {log_ba} = $

$ cn ^ {log_ba} sum_ {j = 0} ^ { lfloor log_b n rfloor – 1} (1- frac {b ^ { lfloor log_bn lfloor}} {n} frac {1} { b-1}) ^ {log_ba} geq $

$ c n ^ {log_ba} sum_ {j = 0} ^ { lfloor log_b n rfloor – 1} (1- frac {1} {b-1}) ^ {log_ba} $

Note iff $ b = 2 $ when $ (1- frac {1} {b-1}) ^ {log_ba} = 0 $ and can not be given as a permissible constant with respect to $ Omega $ (it has to be a positive one).

I tried to prove this special case in other ways, though $ n_j geq frac {n} {2 ^ {j}} – (2 – frac {1} {2 ^ {j-1}}) $ (It is the sum of the geometric progression without limit), but ultimately failed on the same problem.