Questions tagged [asymptotics]

Questions about asymptotic notations and analysis

1,001 questions
Filter by
Sorted by
Tagged with
51 views

Find an asymptotic bound for $T(n)=n^2+T(\frac{n}{2})+T(\frac{n}{4})+T(\frac{n}{8})+…+T(\frac{n}{2^k})$

Given is the following recurrence relation: $T(n)=n^2+T(\frac{n}{2})+T(\frac{n}{4})+T(\frac{n}{8})+...+T(\frac{n}{2^k})$ where $k$ is some constant and $n = 2^t$ for some $t\in \mathbb{Z}$. I'm ...
927 views

Is “super-exponential” a precise definition of algorithmic complexity?

I cannot seem to find a precise definition of what "super-exponential" is supposed to refer to when one's talking about an algorithm's time complexity. For instance, if an algorithm runs for $nC(n-1)$...
29 views

Showing $2^x$ is a lower bound

How do I show that $2^x - x^2 \in \Omega(2^x)$? Basically, I know that this means that $\exists a, x_0 \in \mathbb{R^+}, \forall x \in \mathbb{N}, a.2^x \leq 2^x - x^2$. I worked around a bit with ...
23 views

Big O order of a function

I'm doing some practice questions on Big O notation and came across this question. What is the Big O order of function 𝑓(𝑛) = 𝑛^2 + 𝑛 log2(𝑛) + log2(𝑛). Show your working. My answer is O(n^2) ...
46 views

How to find sets of polynomially bounded numbers whose subset sums are different?

Let $n$ be any positibe integer and set $N=\{1,\dots,n\}$. Now select two arbitrary but different subsets of $N$, say $S$ and $S'$. We are interested in finding a function $\pi(A)=\sum_{i\in A}a_i$ ...
127 views

Is the runtime of binary search big omega of logarithm of n?

My question is that can we say that runtime of the binary search is $\Omega(\log n)$? I know it is both $\Omega(1)$ and $O(1)$ for the best case, and $\Omega(\log n)$ and $O(\log n)$ for the worst ...
63 views

Big O and constants [duplicate]

I've already asked this question on stack overflow, but guys have suggested me to ask my question here. Let's consider classic big O notation definition (proof link): The $O(f(n))$ is the set of all ...
109 views

Calculation of Inorder Traversal Complexity

I want to analyze complexity of traversing a BST. I directly thought that its complexity as $O(2^n)$ because there are two recursive cases. I mean $T(n) = constants + 2T(n-1)$. However, AFAI research ...
87 views

Big-Oh vs Theta in recurrence tree method

I am solving this problem from here. The given relation is $$T(n) = 2 T(\frac{n}{2}) + n^2, \, T(1) = 1$$ The solution via recurrence tree method is given as: The zeroth level has a single node ...
119 views

Asymptotic behavior of $n\sqrt n + n \log n$ & $\log_{100} n$ [duplicate]

I have the following two functions $f(n) = n\sqrt n + n \log n$ $\log_{100} n$ And I need to classify them into the followings: $O(n)$, and/or $O(n^2)$, and/or $O(n^3)$, and/or $O(n^{1.5})$, and/or ...
83 views

Big-O Solving Recurrence Relation by iteration with fractions

I was trying to solve the recurrence relation in order to get a some big-O bound $$B(n) = B(n-4) + \frac{1}{n} + \frac{5}{n^{2} + 6} + \frac{7n^{2}}{3n^{3} + 8}$$ by following the accepted answer ...
110 views

208 views

what is the time complexity for binary division by repeated subtraction?

The divisor and dividend are of length n and m bits respectively. According to Wikipedia article, https://en.wikipedia.org/wiki/Output-sensitive_algorithm division by substraction is an output ...
97 views

Mathematically calculating time complexity

This is a thread about mathematically calculating time complexity of nonlinear functions. I know that those questions were asked a lot, but it didn't make me understand fully the subject. Also I ...
110 views

Big-Oh and Growth Rate

So, in the book I'm studying from it says : The statement “f(n) is O(g(n))” means that the growth rate of f(n) is no more than the growth rate of g(n). What I understood from this statement is ...
61 views

What is the Big-O runtime of this algorithm? [duplicate]

Can anyone explain why the runtime of this is in O(N^3)? Additionally, what would the run-time be in Big-OH if the else statement was removed. ...
33 views

Not able to find any pattern for $4T(n/2)+n^2 n^{1/2}$

I have tried my best but I'm not able to find any pattern for the $n^2n^{1/2}$ part. This question must be solved iteratively and I get totally clueless after two iteration.s I've to find tight bound ...
58 views

83 views

Is the capacity of a hash table a constant value?

In this paper, page 4, it is said: "...there is always a constant expected number of elements that map to the same slot" Assume we have a set $S$ of $n$ values, and we want to insert them into a ...
126 views

Asymptotic bound of a recursive function

Consider the following procedure computing a dummy function. Which one is a correct asymptotic bound for the running time of F(N) expressed in terms of N? ...
126 views

Big O notation: removing big O from denominator

In A First Course in the Numerical Analysis of Differential Equations (page 26) Arieh Iserles gives the following derivation: \begin{equation} \frac{\rho(w)}{\ln(w)}=\frac{\xi+\xi^2}{\xi-\frac{1}{2}\...
468 views

Merge sort worst case running time for lexicographical sorting?

A list of n strings each of length n is being sorted in lexicographical order using the merge sort algorithm. Since we have to take care of comparison of each character in the strings so the merge ...
121 views

Is a sum of n terms considered O(1) or O(n)?

Say I have $n$ numbers in an array and I have to compute the sum of those numbers. Is the complexity considered as $O(1)$ or $O(n)$? Clarification Say I have 10 constants, I could precompute the ...
115 views

Why is $n + 2n^2 + 10n^4 = O(n^5)$?

I'm going through an algorithms text book. One of the questions asks: True or false? $n + 2n^2 + 10n^4$ is $O(n^5)$. This is marked as true. Shouldn't it be $O(n^4)$? What am I missing here?
564 views

Algorithm for using power series to numerically solve a partial differential equation given a boundary condition?

Motivation: Following this discussion about using asymptotic expansions (i.e. polynomial power series) for numerically solving partial differential and algebraic equations (PDAE), I couldn't find any ...
$\tilde \Omega$ for division by logarithmic factor
Is $\Omega \left(\frac{n}{\log{n}} \right)\subset \tilde\Omega(n)$?