The Stack Overflow podcast is back! Listen to an interview with our new CEO.

New answers tagged


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


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


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


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