New answers tagged lower-bounds
1
while (j <= n) is the same as while (j < n+1), and you know how to handle that, right?
So you find the correct solution for the first case, then replace n with n+1 everywhere. You could handle things like while (j+3 <= 2n-4) in exactly the same way, changing it to while (j < 2n-6), finding the solution for the first case, and replacing n with 2n-...
3
$n-j+1$ should work as it satisfied the three properties of a bound function.
It is definitely an integer valued function as all variables and 1 are integers.
Since $j$ is increased by 1 in every iteration, the function decreases by 1 each time. For example let's say $n$ was 5 and $j$ was 4. Then for the first iteration it would be 5-4+1=2, then the second ...
0
It automatically implies that $ O(n^4)$ and $\Omega (n^4)$ because of $f(n)\in O(n^4)$ and master theorem $ \Theta (n^4)$.
2
It seems that you have overlooked the fact that $f(n) \in \Theta(n^4)$ already implies both an upper bound of $f(n)\in O(n^4)$ and a lower bound of $f(n)\in \Omega(n^4)$. Intuitively, $\Theta$- notation says that a function grows "as fast as" another function, which means both "at most as fast" and "at least as fast".
Top 50 recent answers are included
