The solution to $T(n)=T(\log n) + \Theta(1)$ is $O(\log n)$. Does adding $cn$ to this make any difference?
Similarly, is the time complexity of $F(n)=F(\sqrt{n}) + \Theta(1)$ different from $F(n)=F(\sqrt{n}) +cn$ , and if yes what is the difference?
Thanks in advance.
On
The solution of $T(n) = T(\log(n)) + \Theta(1)$ is $T(n)=\log^*(n)$. You are essentially adding a $\Theta(1)$ each time you apply $\log(\cdot)$ to $n$, which you can do at most $\log^*(n)$ times. See iterated logarithm.
$$ T(n) = T(\log(n)) + \Theta(1) = T(\log\log(n)) + \Theta(1) + \Theta(1) = \underbrace{\Theta(1) + \ldots + \Theta(1) + \Theta(1).}_{\text{$\log^*(n)$ times}} $$
For $F(n)=F(\sqrt{n}) + \Theta(1)$ we have $F(n) = \log_2(n)$, since, as before, we add $\Theta(1)$ for each iteration of $\sqrt{\cdot}$ on $n$, which are in total $\log_2(n)$.
$$ F(n) = F(\sqrt{n}) + \Theta(1) = F(\sqrt[4]{n}) + \Theta(1) + \Theta(1) = \underbrace{\Theta(1) + \ldots + \Theta(1) + \Theta(1).}_{\text{$\log_2(n)$ times}} $$
On the other hand, if you set $cn$ in stead of $\Theta(1)$ the first term overpowers everything and you obtain
$$ T(n) = T(\log(n)) + cn = T(\log\log(n)) + c\log(n) + cn = \sum_{i=0}^{i=\log^*{n}}c\: \underbrace{\log\log\cdots\log(n)}_{\text{$i$ times}} = \Theta(n), $$
$$ F(n) = F(\sqrt{n}) + cn = F(\sqrt[4]{n}) + c\sqrt{n} + cn = \sum_{i=0}^{i=\log_2(n)} c\:n^{1/2^i} = \Theta(n). $$
If $c > 0$, a solution of $T(n) = T(\log n) + c n$ can't be $o(n)$, because then $c n = T(n) - T(\log n) = o(n)$.