i’m not sure that im fully understand which recurrece is asymptoticly big tete (n) and which is big teta of (log(n)). im asking becuse in lecture 15 , about adders, guy mentions that the delay of comp - adder is big teta (log(n)) and the recurrence looks like the recurrence of big teta (n).
can you define the differences between the two ?
thanks,
dan levy
I dont understant the question.
use O(n), \Omega(n), \Theta(n) to improve readability
what i mean is that the diffrence between a recurrence that represents a growth of Θ(n) and a recurrence that represents a growth of Θ(log (n)) is unclear to me. if you can show an exemple / format of each function it would be helpful.
f(n)=1+f(n-1) solves to f(n)=\Theta(n).
g(n)=1+g(n/2) solves to g(n)=\Theta(\log n).