8 votes
Accepted

Asymptotics of the sum of a geometric series

There is an abuse of notation in your question: you are using $i$ as both the index for the summation and as the total number of terms in the sum (in the closed formula). Anyway, the ratio of the ...
Steven's user avatar
  • 29.5k
6 votes

Assuming constant operation cost, are we guaranteed that computational complexity calculated from high level code is "correct"?

Yes, this is reasonable as a first cut approximation. As always, there are caveats. A theoretical model is a model. It is used for making predictions, but models typically are not perfect, and there ...
D.W.'s user avatar
  • 159k
6 votes
Accepted

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
  • 15.6k
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
  • 843
3 votes

Which one grows faster, an exponential function where the exponent grows faster than logarithmic or a factorial powered by n?

With some manipulations: $$ f(n) = 4^{n^2 \log n} = (2^2)^{n^2 \log n} = (2^{\log n})^{2n^2} = n^{2 n^2}. $$ and: $$ g(n)= (n!)^n \le (n^n)^n = n^{n^2}. $$ Taking the limit: $$ \lim_{n \to \infty} \...
Steven's user avatar
  • 29.5k
3 votes
Accepted

Big O Notation, Why do we ignore everything inside the log?

By the properties of logarithms: $$\log 3 n^2 = \log 3 + \log n^2 = \log 3 + 2 \log n = O(\log n)$$ and, using $n! \le n^n$ for $n \ge 1$: $$ \log n! \le \log n^n = n \log n = O(n \log n). $$ This ...
Steven's user avatar
  • 29.5k
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
3 votes
Accepted

What does $o_n(1)$ mean?

As I understand it, this $o_n(1)$ is meant as the standard “little o” notation (when $v_n$ takes non-zero values, $u_n = o(v_n)$ means $\frac{u_n}{v_n} → 0$), except that because several variables are ...
Jean Abou Samra's user avatar
2 votes

Assuming constant operation cost, are we guaranteed that computational complexity calculated from high level code is "correct"?

The answer actually depends on the how many machine operations are utilized by an operation of the high-level language. If each operation of $C$ takes a constant machine operations, then the answer ...
Inuyasha Yagami's user avatar
2 votes

Finding asymptotically tight upper bound of a recursion relation

Your upper bound is not tight. Let $n=5^k$, as in you question. You can upper bound your summation by $$ \sum_{i=1}^{k} 5^i \cdot \log^2 5^{k-i} \le 6 \sum_{i=1}^{k} 5^i (k-i)^2 = 6 \cdot 5^{k} \...
Steven's user avatar
  • 29.5k
2 votes
Accepted

Subtracting Two same asymptotic values

I make an example: if $a=\frac{2}{\sqrt{n}}$ and $b=\frac{1}{\sqrt{n}}$, then both are $O(\frac{1}{\sqrt{n}})$ and $a-b=\frac{1}{\sqrt{n}}=O(\frac{1}{\sqrt{n}})= \Theta (\frac{1}{\sqrt{n}})$. If ...
SilvioM's user avatar
  • 843
2 votes

Asymptotic equivalence allows difference by a constant factor?

There are multiple notions/definitions of asymptotic. You need to pick one that is appropriate for your goals. One approach to asymptotics is exactly as you have stated (see, e.g., https://en....
D.W.'s user avatar
  • 159k
2 votes

Solving recurrence by iteration, choosing base case

Well, obviously $T(1),T(2),\dots,T(100)$ are all integers. So, let $c=\max(T(1),T(2),\dots,T(100))$. $c$ is obviously some integer, so it is a constant. So yes, all of those base cases are at most ...
D.W.'s user avatar
  • 159k
2 votes
Accepted

How are pointers modeled on bit-based computer models?

It sounds like you're just asking for the definition of Random-access machine, which is similarly formal to Turing machines, but formally defines how to do "indexing" operations. There's ...
Alex Meiburg's user avatar
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.5k
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
  • 659
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
  • 15.6k
2 votes
Accepted

How to solve the recurrence $ T(n) = 4T\left(\frac{n}{2}\right) + \frac{n}{\lg n} $ in terms of $\Theta$?

If you want to see it explicitly here is the calculation: $T(n)=4T\left(\frac{n}{2}\right) + \frac{n}{\log n}$ implies that the total number of recursions we do is $\log_2 n$. At the pass of the ...
SilvioM's user avatar
  • 843
2 votes

Is $O(n^{f(n)})$ superexponential if $f(n)$ is a polynomial function such that $f(n) > n$ as $n$ approaches $\infty$?

Exponential time is often described as complexity in $\mathcal{O}(2^{p(n)})$ for a polynomial function $p$ rather than $\mathcal{O}(k^n)$. See here for some references. What you describe is the ...
Nathaniel's user avatar
  • 15.6k
2 votes

Time Complexity O-Notation for Kociemba, Korf, and Thistlethwaite's Algorithms? (Rubik cube)

Recall that the time complexity of an algorithm is expressed in terms of its input size. The growth rate of this complexity measure is usually expressed in terms of an asymptotic notation such as Big-...
codeR's user avatar
  • 659
2 votes
Accepted

Time Complexity O-Notation for Kociemba, Korf, and Thistlethwaite's Algorithms? (Rubik cube)

As noted in the answer of codeR Big O notation makes no sense for 3x3x3 alone because of the constant input size. What might be interesting to discuss is the time complexity to find a solution with ...
Herbert Kociemba's user avatar
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
1 vote

Sorting rational numbers in linear time

You can sort an array in linear time if the set of possible array elements is finite. Because in that case you just pick the array elements that have the smallest possible value, then the array ...
gnasher729's user avatar
1 vote
Accepted

Show if $f(n)$ has polynomial growth and $g(n)=\Theta(f(n))$, then $g(n)$ also has polynomial growth

Let us consider only sufficiently large values of $n$. As you have pointed out there are two constants $c_1, c_2$ with $0< c_1 \le c_2$ such that: $$ c_1 f(n) \le g(n) \le c_2f(n). $$ Also, since $...
Steven's user avatar
  • 29.5k
1 vote
Accepted

Conflicting definitions surrounding asymptotic notations. Please advise!

The two definitions are equivalent and it is not true that $n^2 - 3n + 4 = o(2 \cdot n^2)$. The arbitrary positive $\varepsilon$ in the definition is a real number, not just positive integer. For ...
Vladimir Lysikov's user avatar
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

Expected number of mistakes grows logarithmically in number of iterations - improving performance?

Yes, it becomes clear if you see the error ratio: $$r_T := \frac{T}{\log T} \ .$$ $r_T$ is a monotonic (strictly) decreasing sequence and $\lim\limits_{T\to 0} r_T = 0$, but $r_T>0 \ \forall \ T &...
SilvioM's user avatar
  • 843

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