Questions tagged [asymptotics]

Questions about asymptotic notations and analysis

Filter by
Sorted by
Tagged with
4
votes
2answers
288 views

Lower bound of a summation with an exponential

For the following (related to a binary tree complexity question): $$f(n) = \sum_{h=0}^{\lg{}n} h2^h$$ Is there any way to express this only in terms of $n$? Or approximate it? Put in another way, I ...
4
votes
2answers
85 views

Origins of misconception about using equality signs with Landau notation

From "Misconception 1" from Søren S. Pedersen's blog, and as many have seen before, a major misconception in Big-O (and others) notation is to say a function is "equal" to Big-O of some other function:...
4
votes
4answers
2k views

Why does merge sort run in $O(n^2)$ time?

I have been learning about Big O, Big Omega, and Big Theta. I have been reading many SO questions and answers to get a better understanding of the notations. From my understanding, it seems that Big O ...
4
votes
1answer
347 views

Why is log(n/p) asymptotically less than log(n)/log(p)

I'm trying to figure out which is better asymptotic complexity, $O(\log{\frac{n}{p}})$ or $O\left(\frac{\log{n}}{\log{p}}\right)$. $p$ is the amount of parallelism (i.e. number of cores), and $n$ is ...
4
votes
4answers
3k views

Why do we use big O rather than $\Omega$ when discussing best case runtime?

When discussing the worst case runtime $T(n)$ of an algorithm, we attempt to bound $T(n)$ above by some simple function $g(n)$, so that $T(n) = O(g(n))$. When discussing the best case runtime $T(n)$ ...
4
votes
2answers
333 views

Is Ω(f+g) = Ω(min(f,g))?

We know that $O(f(n)+g(n))=O(max(f(n),g(n)))$. So can we say that $\Omega(f(n)+g(n)) = \Omega(min(f(n),g(n))$? Then what is $\Theta(f(n)+g(n))$ equal to?
4
votes
3answers
253 views

If $f$ and $g$ are increasing functions, are we guaranteed that $f=O(g)$ or $g=O(f)$? [duplicate]

Given two increasing functions $f$ and $g$ with values in the natural numbers, is it always the case that either $f\in O(g)$ or $g\in O(f)$. If the statement is true, then can anyone provide a ...
4
votes
1answer
2k views

Algorithms with polynomial time complexity of higher order

I was learning about algorithms with polynomial time complexity. I found the following algorithms interesting. Linear Search - with time complexity $O(n)$ Matrix Addition - with time complexity $O(n^...
4
votes
2answers
112 views

When is this even possible (even for a dense graphs) $|E| = \Theta (|V|^2)$

Wikipedia says that "a dense graph is a graph in which the number of edges is close to the maximal number of edges." and "The maximum number of edges for an undirected graph is $|V|(|V|-1)/2$". Then ...
4
votes
3answers
385 views

Is $\Omega(\sqrt{n}!)=\Omega(2^{\sqrt{n}})$ correct?

I'm very confused when I see the following statement in the famous CLRS book "Introduction to Algorithms (3rd)", ch34.2, page 1063: ...and therefore the running time is $\Omega(m!)=\Omega(\sqrt{n}!)...
4
votes
1answer
52 views

Lower bound on $1^k+2^k+\dots+n^k$

I calculated the worst case scenario of a time complexity of an algorithm problem using recurrence tree. (The problem cannot be solved by master theorem.) Now I want to find a lower bound on the ...
4
votes
3answers
1k views

Big O Notation of $n^{0.999999}\log(n)$

I'm taking the MIT Open Courseware for Introduction to Algorithms and I'm having trouble understanding the first homework problem/solution. We are supposed to compare the asymptotic complexity (big-O)...
4
votes
2answers
249 views

Is asymptotic ordering preserved when taking log of both functions?

In one of my exercise sheets I have the following question; Let $f,g\colon \mathbb{N}\longrightarrow\mathbb{R}$ be positive functions with $f(n) \in O(g(n))$. Prove or disprove; $\ln(f(n)) \in O(\ln(...
4
votes
1answer
167 views

What can be said about Θ-classes in m and n if we know that m < n?

A function in $\Theta(m + n^2)$ and $0 < m < n^2$, is in $\Theta(n^2)$. Does a function in $\Theta(m\log n)$ and $0 < m < n^2$, imply that it is $\Theta(n^2\log n)$?
4
votes
1answer
78 views

Asymptotics of $\frac{1}{\log(\frac{2^n}{2^n-1})}$

I am trying to understand the asymptotics of \begin{equation} f(n) = \frac{1}{\log(\frac{2^n}{2^n-1})} \end{equation} In particular, is there some $c \geq 1$ such that $f(n) = O(n^c)$?
4
votes
1answer
2k views

Complexity of division

The article Computational complexity of mathematical operations mentions that the complexity of division in $O(M(n))$, and that "$M(n)$ below stands in for the complexity of the chosen multiplication ...
4
votes
5answers
8k views

How to prove any polynomial of degree $k$ is in $\Theta(n^k)$?

I want to prove that any polynomial of degree $k$ is in $\Theta(n^k)$. The coefficient of $n^k$, $a_{k}$, is positive. I know I need $0 \leq c_{1}n^k \leq a_{k}n^k + ... + a_{0} \leq c_{2}n^k$ for ...
4
votes
1answer
145 views

If a one-way functions (OWF) exist, then there exits a OWF that is computable in quadratic running time by a padding argument

I believe this question should be extremely easy but I am having a (embarrassing) hard time figuring out why its true if there exist OWF (computable in polynomial time) then there exits a OWF that is ...
4
votes
1answer
1k views

Recursive equation for complexity: T(n) = log(n) * T(log(n)) + n

For analyzing the running time of an algorithm , I'm stuck with this recursive equation : $$ T(n) = \log(n) \cdot T(\log n) + n $$ Obviously this can't be handled with the use of the Master Theorem, ...
4
votes
1answer
2k views

Trouble understanding how to pick constants to prove big theta

So I'm reading Introductions to Algorithms and sometimes I wish it would be a little bit more friendly with how it explains topics. One of these topics is proving big-theta. I understand that the ...
4
votes
2answers
72 views

Order Mistake Definition in CLRS

On page 53 or CLRS it has said : We can extend our notation to the case of two parameters n and m that can go to infinity independently at different rates. For a given function $g(n,m)$, we denote ...
4
votes
2answers
162 views

Asymptotic analysis of a real-valued function involving complex numbers

I have an algorithm which computes the size of maximum independent set of a graph $G(V, E)$. Let $n=|V|$ be the number vertices, $m=|E|$ be number of edges, and denote the size of maximum independent ...
4
votes
3answers
955 views

Run time of recurrence with five uneven calls

I am trying to figure how to find an upper bound for the running time of a given recurrence relation (without proving the bound) using the Iteration method. The recurrence is: $$T(n)=2T\left(\frac{n}{...
4
votes
2answers
140 views

Asymptotic behavior of functions with not analytic expression

Is it in general acceptable by computer science community, if the run-time or space consumption of an algorithm is derived by experiment and not analytically? For example let's say we have an ...
4
votes
1answer
71 views

Is it enough to show the number of steps for certain values of $n$ in order to state an algorithm's complexity?

If I can easily state the number of steps for an algorithms for certain values of $n$, e.g. for $n = 2^k$, where $k$ is a whole number, the number of steps is $n\log n$, is this enough to allow me to ...
4
votes
1answer
106 views

How to resolve a recurrence relation in the form of $T(n) = T(f(n))*T(g(n)) + h(n)$

I am basically trying to solve the following question: Given a set $P = \{\{1\},\{2\},\dots,\{n\}\}$ of $n$ sets of elements, our aim is to merge these elements into one set. At each step, sets can ...
4
votes
1answer
77 views

About a step in the analysis of Quicksort by Sedgewick and Wayne [duplicate]

In the book Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne, when they are analyzing quicksort (page 294), they present the sequence of transformations: $$\begin{gather*} C_N = N + 1 + (...
4
votes
1answer
80 views

Which bound is better, a logarithmic or a polynomial with arbitrarily small degree?

I have a randomized approximation algorithm which can be tuned by selecting the randomization probabilities. I found out that: For any $\epsilon >0$, there are probabilities for which the ...
4
votes
1answer
574 views

Is the DPLL algorithm complexity in terms of # of clauses or # of variables?

I'm a bit confused how worst case complexity is estimated for the DPLL algorithm. Is it in terms of number of clauses, number of variables, or something else?
4
votes
1answer
3k views

Time complexity based on two variables

Suppose we have a function based on two inputs of length $m,n$. Therefore the time complexity of the function is calculated by $T(m,n)$. Suppose that we have: $T(m,c)\in O(m^2)$ for any constant $c$. ...
4
votes
1answer
121 views

Solving $T(n) = 2T(n/2) + T(n-1)/\log n$

I am interesting in the asymptotic rate of growth of the following recursion: $$ T(n) = 2T(n/2) + \frac{T(n − 1)}{\log n}, $$ with base case $T(1) = 1$. I'm having trouble of solving this recurrence ...
4
votes
1answer
596 views

What does $|V|=O(|E|)$ mean?

I was reading about Dijkstra's algorithm from this Stanford University lecture presentation. On page 18 it says Dijkstra's algorithm is $O(|V|\log|V|+|E|\log|V|)$ and I understand why. But then it ...
4
votes
1answer
767 views

How to solve for p in Akra-Bazzi method for analyzing time complexity?

Every single online resource I've looked up on Akra-Bazzi method appears to skip over the same step: They say you have to solve for $p$ without explaining how. If you look up the various PDFs and ...
4
votes
1answer
170 views

What's the formal definition of Big-O notation for functions of more than one variable?

For functions of a single totally ordered variable, I already know that $f(n)$ is $O(g(n))$ if and only if $\exists m. \exists c. \forall n. (n \ge m) \rightarrow [ f(n) \le c \cdot g(n) ]$. What I ...
4
votes
2answers
7k views

If f(n) = O(g(n)), then is log(f(n)) = O(log(g(n)))?

I guess this is true, because log is a strictly increasing function, but how do I prove it formally? I tried something like: Let $f(n)$ and $g(n)$ be monotonically increasing functions, $c \in \...
4
votes
1answer
98 views

Solving a system of recurrences

If the time complexity $T(n)$ of two functions $x(n)$ and $y(n)$ are mutually recursive, as in Time complexity of mutually recursive functions, this gives $T(n)=O(2^n)$. But how do you measure an ...
4
votes
1answer
218 views

Doubt with a problem of grown functions and recursion tree

I'm confused to conclude the recursion tree method a guess for the next recurrence: $$T(n)=3T\left (\left\lfloor \frac{n}{2}\right \rfloor\right) +n$$ I write some costs for the levels of tree, you ...
4
votes
1answer
283 views

Recursion Tree Analysis by Leaves

Assumptions Let's say we have any recurrence relation (however this is perhaps more applicable to "unpredictable" recurrence relations): $$T(n) = \;?$$ For example: $$T(n) = aT\left(\frac{n}{b}\...
4
votes
1answer
563 views

Median-of-medians in O(log n) memory

Is there a way to use median-of-medians to find a median in, simultaneously, ​ ​O(log n) ​ ​memory and O(n) comparisons? The user orlp on this site seems to claim that there is. Getting ​ ​O(log n) ...
4
votes
1answer
1k views

how to understand time complexity from a plot?

This is my first question here. I'm not a CS at all, so it might be quite trivial. I have written a program in C where I allocate memory to store a matrix of dimensions n-by-n and then feed a linear ...
4
votes
1answer
91 views

A totally-ordered set of functions

When we analyze algorithms using the $O$ notation, we usually use only a small set of the space of all functions. E.g., we use $\Theta(n)$ but not $\Theta(2n)$, as these two are equally well ...
4
votes
1answer
124 views

Height of AVL after entries

Problem: Suppose $V$ is an AVL tree (a self-balancing binary search tree) of $n$ elements. After the insertion of $n^2$ elements, what would be its height? My idea: the height of an AVL tree is ...
4
votes
0answers
113 views

Name for function in big O but not in little o?

Let $f(n) = O(g(n))$, but not $f(n) = o(g(n))$. That's a nice property, because it means that we cannot replace $g(n)$ with a substantially smaller function. Is there a name for this choice of $g(n)$? ...
3
votes
1answer
3k views

Is log(n) in complexity class P?

$\log(n)$ is not polynomial; is a problem solvable in $\mathcal{O}(\log n)$ time in P? $n\times \log(n)$ is also not polynomial; is a problem solvable in $\mathcal{O}(n\times \log n)$ time in P? If ...
3
votes
5answers
834 views

What does big O mean as a term of an approximation ratio?

I'm trying to understand the approximation ratio for the Kenyon-Remila algorithm for the 2D cutting stock problem. The ratio in question is $(1 + \varepsilon) \text{Opt}(L) + O(1/\varepsilon^2)$. ...
3
votes
2answers
2k views

Is $\log(n!)$ in $\Theta(n \log(n))$?

I had two questions on my automated test which I don't understand the answer for. $\log(n!) = \log(n\cdot (n-1)\cdot \cdots \cdot 2\cdot 1) = \log(n)+\log(n-1)+....+\log(1)$. So it is in $O(n\log(...
3
votes
4answers
209 views

Describing the asymtotic complexity of processing two-dimensional data structures

Consider the following Python function: ...
3
votes
3answers
493 views

What is the notation for bounding running time in worst case with concrete example resulting in that worst case running time

I know that Big O is used to bound worst case running time. So an algorithm with running time $O(n^5)$ means its running time in worse case is less than $n^5$ asymptotically. Similarly, one can say ...
3
votes
2answers
360 views

Conflicting definitions of quasipolynomial time

The textbook The Nature of Computation uses the following definition of quasipolynomial time: A quasipolynomial is a function of the form $f(n) = 2^{\Theta(\log^k n)}$ for some constant $k > 0$...
3
votes
2answers
4k views

The order of growth analysis for simple loop

What would the order of growth for this loop be: int sum = 0; for (int n = N; n > 0; n /= 2) for(int i = 0; i < n; i++) sum++; The first loop ...

1 2 3
4
5
22