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 ...
1
vote
1answer
63 views

Time Complexity for $T(n) = T(\sqrt{n}) + 1$

$$T(n) = T(\sqrt{n}) + 1$$ I am trying to find the time complexity of the given equation. I tried everything that I know but I could not find the answer. What I've tried: $k = lg(n)$ and $n=2^k$ -> ...
1
vote
3answers
81 views

Time Complexity in $\theta$ Notation

$$T(n) = 2T\left(\frac{n}{2}\right) + T\left(\frac{n}{4}\right) + 5$$ What is the time complexity of the given algorithm in $\theta$ notation. Thanks in advance.
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 + ...