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).