1
vote
2answers
29 views

Asymptotic notation: A function is Θ-Notation

H. Cormen, Exercise 3.1-2 The following statement is true? If yes, prove that it is true. $$ (n+a)^b = Θ(n^b)\\ a, b \in R\\ b>0 $$ I tried to expand $(n+a)^b$ using the Binomial theorem, but ...
0
votes
1answer
28 views

Is $f(n) + O(f(n)) = \theta(f(n))$?

I've been asked to show whether this is always, never or sometimes true. I think I understand that in this situation, $O(f(n))$ can be treated as a macro for some function $g(n)$. So if the equation ...
0
votes
0answers
21 views

Max Function Notation [duplicate]

I've been asked whether the following is always, never or sometimes true: $f(n) + g(n) = \theta(\max(f(n), g(n)))$ I understand the definition of theta notation, but I'm not sure how to read the ...
0
votes
2answers
48 views

Algorithm analyse with Theta notation

Is $(n \log n) + \frac{\lfloor (\log n)^2\rfloor + \log n}{2} = \Theta(n \log n)$ ? My solution: $$ \begin{aligned} c_1 \cdot (n \log n) \le\,& (n \log n) + \frac{\lfloor(\log n)^2\rfloor + ...