New answers tagged

0

Here is an argument by substitution: $$\begin{aligned} T(n) &= 3T(n/2)+2n \\&= 3(3T(n/4)+n)+2n \\&= 3(3(3(T(n/8)+n/2)+n)+2n \\&= \cdots \\&= 3^kT(n/2^k)+\sum_{i=0}^{k-1}{2n\left(\frac{3}{2}\right)^i} \\&= 3^kT(n/2^k)+2n\frac{\left(\frac{3}{2}\right)^k-1}{\left(\frac{3}{2}\right)-1} \\&= 3^kT(n/2^k)+4n\left(\frac{3}{2}\right)^k-4n \...


2

Word "asymptotic" is used to emphasize the condition $\exists n_0\in \mathbb{N}$ $\forall n> n_0$ for inequality $0\leqslant f(n) \leqslant C g(n)$ and generally does not contain any mention of limit or asymptotic. Even well known definition of O big, using $\lim\sup \frac{f}{g}$, have sense only when limit point for O big is not limit point ...


1

The technical meaning of asymptotic upper bound is given by the definition of big O. That is, $g(n)$ is an asymptotic upper bound on $f(n)$ if $f(n) = O(g(n))$ according to the definition you wrote. The term asymptote may have other meanings in other circumstances. For example, in analytic geometry, an asymptote of a function $f(x)$ is either a line $\ell(x)$...


2

Firstly let me say, that in definition of big-O, for non negative case, there is inequality(not equality, typo I think): $$O(g)=\{f: \exists C>0, \exists N \in \mathbb{N}, \forall n> N, f(n)\leqslant C g(n)\}$$ Now $f(n) = c\cdot g(n) + O(g(n))$ means, that $\exists \phi (n) \in O(g(n))$ such that $f(n) = c\cdot g(n) + \phi (n)$. From here we have $$...


0

$$T(n)= 5T\left(\frac{n}{4}\right) + n^2 = 5^2T\left(\frac{n}{4^2}\right)+\left(\frac{5}{16}+1\right)n^2=\\=5^3T\left(\frac{n}{4^3}\right)+\left(\left(\frac{5}{16}\right)^2+\frac{5}{16}+1\right)n^2=\cdots=\\ =5^kT\left(\frac{n}{4^k}\right)+\left(\left(\frac{5}{16}\right)^{k-1}+\cdots +\frac{5}{16}+1\right)n^2$$ If you have some initial condition for $T(1)$ ...


1

Take $f(n) = n^4$. For this function, if you double the argument, the result is multiplied by 16, that is by a constant factor. Now take $g(n) = 2^n$. For this function, if you double the argument, the result is squared, and since $2^n$ can grow arbitrarily large, there is no limit to the growth factor achieved by squaring g(n). That’s the difference. If the ...


0

For given $f(n)$, well defined, for $\forall n\in \mathbb{N}$, the function $f(n/x)$ can be even undefined: for example $f(n)=\frac{1}{n-\frac{1}{2}}$ and $x=2$. More sophisticated example is $$ f(n)=\begin{cases} 2^k, & n=2k+1 \\ k, & n=2k \end{cases} $$ Obviously $f(2n) \in \Theta(n)$, but $f(n)\notin \Theta(n)$. Case, where your sentence is true ...


1

Suppose $f(n) = 2^n$. Then $f(n / 2) = 2^{n / 2} = \sqrt{2^n}$ and setting e.g. $g(n) = 2^n$ as well shows $f(n) \in \Theta(g(n))$ but $f(n / 2) \notin \Theta(g(n))$, so this does not hold in general.


0

I will answer partially: we may use big-Oh notation when we want to have guarantees on how long an algorithm is going to run. That is the main concern of many algorithms designers and it may somewhat explain why this notation is the most popular amongst Landau Notation.


3

Your recurrence can be solved using the Akra–Bazzi theorem, a vast generalization of the master theorem. The result is $\Theta(n\log n)$. You can also see this using a recursion tree. The root is labeled $n$. An internal vertex $m$ has children labeled $m/5$ and $4m/5$. Vertices are leaves if their labels is at most some arbitrary positive constant $C$, say $...


0

Your constant $c$ needs to satisfy $$ \frac{5}{16} c n^2 + n^2 \leq c n^2, $$ that is, $$ \frac{5}{16} c + 1 \leq c. $$ Hopefully you can determine the set of constants $c$ for which this inequality is satisfied.


2

It's well known task "Checking for Duplicates" and you can found it for example in Tim Roughgarden - Algorithms Illuminated_ Part 1_ The Basics-(2017) 42 page. Let me say, that as here so in book taking last index "i" as $n=$"array.length()" have no sense, because then index "j" runs out of borders. But this do not ...


2

The time complexity of an algorithm depends on the model of computation. Algorithms are usually analyzed in the RAM machine, in which basic operations on machine words (such as assignment, arithmetic and comparison) cost $O(1)$. A machine word has length $O(\log n)$, where $n$ is the size of the input. In your case, the size of the input is at least $n$ (...


1

Firstly let me bring little more exactness. In sentence If I understood this definition right, it would mean that I can say; for a function $f(n) = n$ then $n$ is big-oh of $n^2$ because $n \leq 1\cdot n^2$ for any $n_0$. is used "any $n_0$", but in definition of $O$ we have $\exists n_0$ - existence is essential. To clear your doubts, hope, ...


4

This is not a simple question, and you shouldn't expect a simple answer. There are a range of similar questions in this space: why do we study asymptotic running time? why do we use asymptotic running time analysis to analyze algorithms? why do we study complexity theory? Each of those has multiple answers; there is not just a single reason why we do it, ...


1

The statement $n = O(n^2)$ is true. There is nothing wrong with it. Maybe you're thinking of the Theta notation.


1

You correctly pointed out that $\ln n = \frac{\log_2n}{\log_2 e}$. You can rewrite this as $\ln n = \frac{1}{\log_2e}\cdot\log_2n$. Since $\Theta(\cdot) $ allows you to drop constant factors (and as @Pseudonym pointed out, $\frac{1}{\log_2e}$ is constant), it follows that $\ln n = \Theta(\log_2n)$


0

Let the probability that the key is found be $p$. Then in case of a miss (probability $1-p$), we perform $n$ comparisons, in case of a hit (probability $p$), we perform from $1$ to $n$ comparisons with equal probability. Hence the expected number of comparisons is $$(1-p)n+\frac{n+1}2p=\frac{(2-p)n+p}2.$$ In Landau's asymptotic notation, this is $\Theta(n)$...


0

Let us recall the definition of big-O notation. If a function g(n) = O(f(n)), this implies that there exists two positive constants n0 and c, such that for all n > n0, 0 ≤ g(n) ≤ c f(n) Hence, it follows that O(n) is equivalent to O(n/2), as n is just n/2 multiplied by a constant factor, which in this case is 2.


Top 50 recent answers are included