6 votes

Possible Mistake in Skiena's Algorithm Design Manual

You are totally right, though I think there is an easier proof: if $m = n$, then $mn-m^2 +m= m\notin \Omega(m^2)$. However, since the analysis is done when searching for a worst case, you could just ...
Nathaniel's user avatar
  • 13.7k
5 votes

Big-O time complexity for this code snippet

You are right, the two innermost loops perform $\Theta(\log n)$ iterations each, so we have a total of $\Theta(\log^2 n)$ iterations, which are repeated $\Theta(n)$ times in the outer loop, which ...
SilvioM's user avatar
  • 808
3 votes
Accepted

Big O, Understanding when the increment is doubling

The inner loop: After k iterations we have $j = 3 \cdot 2^k$. We exit the loop if $3 \cdot 2^k \ge 4 \cdot i^3$ or $2^k \ge (4/3) \cdot i^3$ or $k \ge \log (4/3) + 3 \cdot \log i$. So we add $\log (4/...
gnasher729's user avatar
  • 29.4k
2 votes
Accepted

Big O notation of $O(n/(m-n))$

You cannot make a better conclusion in the general case: if $m$ is almost $n$ (not equal to $n$, otherwise $\frac{n}0$ is not defined), then it is $\mathcal{O}(n)$; if $m$ is big enough compared to $...
Nathaniel's user avatar
  • 13.7k
2 votes
Accepted

Bound $T$ asymptotically tight | Recursive trees

We can directly approach this problem using the recurrence tree method. Let us now denote $1-\alpha$ as $\beta$ for notational clarity. For any constant $l\ge2$ we have, $\alpha^l+\beta^l < 1$.     ...
codeR's user avatar
  • 98
2 votes

Bound $T$ asymptotically tight | Recursive trees

Using the Akra-Bazzi method we have that $ \alpha^p + (1-\alpha)^p = 1 $ for $p=1$, and that: $$ \int_1^n \frac{x^l}{x^{p+1}} \, \text{d}x = \int_1^n x^{l-2} \, \text{d}x= \frac{x^{l-1}}{l-1} \,\bigg|...
Steven's user avatar
  • 29.3k
1 vote

Big O notation of $O(n/(m-n))$

n / (m-n) is undefined for m = n. It is equal to +/- n if m = n +/- 1. But for example for m = 0 or m = 2n it is just +/- 1. You can’t really simplify this. For fixed n, you have a function that goes ...
gnasher729's user avatar
  • 29.4k
1 vote

Solving recurrence by iteration, choosing base case

If you have a recurrence that doesn’t apply to the case n = 1, then it would be correct to assume T(1) = c, for some unknown c, and resolve the recurrence based on that; this would be useful if you ...
gnasher729's user avatar
  • 29.4k
1 vote

Is the time complexity of a loop that simultaneously increments and multiplies $O(\log_k n)$ when $k = 1$?

In the incomplete GeeksForGeeks question #8, it is only correct when $k > 1, k \in \mathbb{Z}$. The code is equivalent to for(int i=0;i<n;i=1+i*k). We can ...
Kenneth Kho's user avatar
1 vote

Ω(f(x)) and worst case analysis

One thing I would like to add is that $O$, $\Omega$, $o$, $\omega$, and $\Theta$ are all about relating functions to one another. In particular for functions $f$ and $g$, $f(x)\in O(g(x))$ says that (...
NaturalLogZ's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible