The Stack Overflow podcast is back! Listen to an interview with our new CEO.

Questions tagged [asymptotics]

Questions about asymptotic notations and analysis

Filter by
Sorted by
Tagged with
1
vote
1answer
35 views

Represent polynomial time complexity as linearythmic

To determine the experimental time complexity of radix sort, I wrote a program that counted the number of steps the algorithm took to sort N points. I ran that program for multiple N length arrays, ...
0
votes
1answer
107 views

Show that $T(2^n) = \Theta(3^n)$ [duplicate]

We have a function $T(n)$ defined by $T(1) =1$ and $T(n)=3T(\lfloor n/2\rfloor)+n$ for $n > 1$. We need to show that $T(2^n)=\Theta (3^n)$. How should I approach this question? Any suggestion?
1
vote
1answer
535 views

Big-O with nested loops and “variables” in the T(n)

So, I need to find the T(n) and then Big-O (tight upper bound) for the following piece of code: ...
1
vote
1answer
377 views

Introductory explanation of the Big-Oh properties

I've noticed that Big-Oh notation actually has some properties such as summation, product but i couldn't find an introductory explanation for their use or how they can help to solve asymptotic ...
1
vote
1answer
28 views

Is this correct in term of big-oh notation: given $g = O(f)$ and $h = O(f)$ can we say $g = O(h)$?

We have two equations $g = O(f)$ and $h = O(f)$ , then can we derive that $g = O(h)$. I came up with following proof but i dont know it's correct or not. $$g = O(f)$$ $$g \le c_1*f $$ $$h \le c_2*f $$ ...
1
vote
1answer
42 views

Asymptotic bound of a heap's height

Today I was taught that since the height of a heap cannot exceed $\log n$, it is $O(\log n)$; height in my class was defined as the maximum number of steps in a simple path from a leaf to the root. ...
1
vote
1answer
67 views

Master theorem recurrence relation

Consider I have the following recurrence $$T(n) = 10T(n/3) + \Theta(n^2\log^5 n)\,.$$ Now, by the master theorem, if we evaluate $n^{\log_{b}{a}}$, we get $n^{\log_{b}{a}} = n^{\log_{3}{10}} = n^{2....
0
votes
1answer
211 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 ...
1
vote
1answer
111 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 ...
1
vote
2answers
2k views

What is the Big Theta of $(\log n)^2-9\log n+7$? [duplicate]

How can I find the Big Theta of $(\log n)^2-9\log n+7$? I thought of $(\log n)^2-9\log(n)+7 < c_1(\log n)^2 +7$ or something like this and can't find the right way.
-1
votes
2answers
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. ...
4
votes
3answers
2k views

Show that $\log n = o(n^\epsilon)$

I am trying to understand how to prove that a polynomial will always grow faster than a logarithm. $\log n = o(n^\epsilon), \epsilon>0$ Intuitively, it is obvious, and plugging in a few numbers ...
0
votes
1answer
288 views

In asymptotic notation how to prove that $\mathcal{O}(g(n))\subseteq\mathcal{O}(f(n))\implies\mathcal{O}(f(n)+g(n))=\mathcal{O}(f(n))$

I have to prove that $$\mathcal{O}(g(n))\subseteq\mathcal{O}(f(n))\implies\mathcal{O}(f(n)+g(n))=\mathcal{O}(f(n))$$ The functions are non-negative. Clarification: $$\mathcal{O}(f(n)+g(n))=\...
2
votes
2answers
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 ...
1
vote
2answers
58 views

What does ∈ mean in the exponent?

I'm having troubles understanding the following proof: $$ \begin{align*} &\text{Proof: } \forall \epsilon \in \mathbb{R}^+, \forall a \in \mathbb{Z}^+, n^\epsilon \gg \log_a(n) \\ &\...
5
votes
5answers
12k views

How do I show T(n) = 2T(n-1) + k is O(2^n)?

This is a practice problem I've come up with in order to study for an exam I have in a couple of hours. Again, here's the problem: Show T(n) = 2T(n-1) + k is O(2^n) where k is some positive constant. ...
3
votes
1answer
737 views

Use of Big-O Notation: Size of Input vs Input

It is my understanding that, when one is describing time complexity with $\mathcal{O}$, $\mathcal{\Theta}$, and $\mathcal{\Omega}$, one must be careful to provide expressions with regards to the size ...
4
votes
3answers
2k 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)$ ...
6
votes
3answers
10k views

Confused about proof that $\log(n!) = \Theta(n \log n)$

So I was able to show that: $\log(n!) = O(n\log n)$ without any problems. My question is when trying to prove that $\log (n!) = \Omega(n\log n)$. I was able to show that: $$\begin{align*} \log n! &...
3
votes
1answer
69 views

Removing arithmetic within recurrences

A similar question was asked here: Solving recurrences using substitution method, but I am still somewhat hazy as to how this process works. Say, for $T(n) = T(\lceil n/5 \rceil + 36) + n \log n$ ...
3
votes
1answer
159 views

Asymptotic analysis of a summation

I was calculating the time complexity of one of the phases of my proposed algorithm, but unfortunately, I faced a problem about solving that and providing an understandable running-time. This phase of ...
0
votes
1answer
117 views

Exponential nested Loop Big O complexity calculation [duplicate]

Can I get a bit of help over here, I can't seem to get to a finish point with this code complexity. I have trouble with making notations, exponential ones in particular..... I spent hours with this ...
0
votes
1answer
30 views

complexity class of functions [duplicate]

What would these statements mean if f(n) and g(n) are functions over natural numbers? g(n) is in Θ(f(n)). and An algorithm is in the complexity class Θ(f(n)).
1
vote
1answer
54 views

Understanding this explanation about Big O notation

I'm trying to learn the Big O Notation...and I got a bit confused by this article: https://brilliant.org/practice/big-o-notation-2/?chapter=intro-to-algorithms&pane=1838 where it stands that f(...
1
vote
3answers
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 ...
2
votes
1answer
25 views

How to solve $T(n)\leq n^2+n\left[T(n-m)+T(m-1)\right]$?

I am trying to find $T(n)=O(f(n))$, where $$T(n)\leq n^2+n\left[T(n-m)+T(m-1)\right],$$ where $m\in\{1,2,\ldots,n\}$. Is it possible to find $f(n)$ such that $T(n)=O(f(n))$? I started to fix $m=n/2$...
1
vote
1answer
127 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? ...
5
votes
2answers
127 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}\...
2
votes
1answer
122 views

Find the asymptotic bound $\Theta$ of $t(n)=t(\frac{n}{5})+t(\frac{n}{17})+n$

Find the asymptotic bound in terms of $\Theta$ (Theta) using the master theorem for the following recursive equation. Assume that $t(n)= \Theta (1)$ for suffucuently small $n$. $$t(n)=t(\frac{n}{...
5
votes
1answer
469 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 ...
3
votes
1answer
342 views

Big-O / $\tilde{O}$ -notation with multiple variables when function is decreasing in one of its arguments

Say we have an algorithm that takes an input a triple ($X$, $A$, $\epsilon$), where $X$ is a sequence of $n$ bytes, of which the algorithm might query only a subset, and $A$ and $\epsilon$ are ...
2
votes
1answer
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 ...
1
vote
1answer
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?
5
votes
1answer
565 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 ...
-1
votes
2answers
131 views

Will we ever achieve a $O(n)$ general purpose sorting algorithm (or at least better than $O(n\log(n)))$?

I've been thinking about this question ever since I learnt about the $O(n\log(n))$ sorting algorithms such as MergeSort, QuickSort (average case is pretty much worse case with a good choice of a pivot)...
1
vote
1answer
81 views

$\tilde \Omega$ for division by logarithmic factor

Is $\Omega \left(\frac{n}{\log{n}} \right)\subset \tilde\Omega(n)$?
8
votes
2answers
1k views

Double exponentials vs single exponentials

Here are four tenets I cannot reconcile: Double exponential time algorithms run in $O(2^{2^{n^k}})$ time with $k \in \mathbb{N}$ constant Exponential time algorithms run in $O(2^{n^k})$ with $k \in \...
1
vote
3answers
81 views

What is the constant $C$ in the definition of asymptotic notations?

For example in the definition of $\Theta$: $f(n) = \Theta(g(n)$ if there exist positive constants $c_1, c_2$ and $n_0$ such that $$ 0 \leq c_1 \cdot g(n) \leq f(n) \leq c_2 \cdot g(n) \text{ for ...
0
votes
1answer
41 views

How to describe an algorithm whose input size diminishes by 1 for each iteration

To elaborate on the title: I have a recursive algorithm whose input is reduced by 1 for every iteration until the input size is 1. 1st iteration: n 2nd iteration: n-1 3rd iteration: n-2 4th ...
3
votes
2answers
165 views

Solving recurrences by substitution

I'm going through Cormen et al.'s Introduction to Algorithms and I am a little thrown off by some of the subtleties of solving recurrences with the substitution method. Given the recurrence: $$ T(n) ...
1
vote
2answers
2k views

Can an algorithm run in “O(n/a)” time?

On one hand, it seems to make no sense, because of the following: When expanded, the claim $f(n,a) \in O(n/a)$ would be There exist $C > 0$, $n_0$, and $a_0$ such that if $n \geq n_0$ and $a \...
1
vote
1answer
341 views

How to get the upper, lower and average bound of a given algorithm?

How to get upper, lower, average bound of given algorithm? What should be the first step I should do? I search on the internet and only give me the definition of those 3. For example if take the ...
1
vote
1answer
45 views

What is +1 in binary search time complexity

Why is binary search time complexity for worst case log (n) + 1 instead of just being log(n)? the way I understand it, the number of times we divide the list till we find our desired element is log (n)...
1
vote
1answer
67 views

What is the complexity of this algorithm for sparse matrices?

I am reading a paper on sparse matrices and there is an algorithm for sparse lower triangular systems. In the below pseudo-code $l$ is a sparse matrix and $x,b$ are sparse vectors. ...
0
votes
3answers
69 views

Fibonacci Series with Dynamic Programming

We can compute Fibonacci numbers by means of dynamic programming approach. If we do not store intermediate solutions, we cannot use them for future necessities. In this case, asymptotic complexity ...
1
vote
2answers
230 views

Time complexity of Rabin-Karp algorithm

$n$ : length of text T $m$ : length of pattern P When I study Rabin-Karp algorithm, I learned the best case of this algorithm is $\theta(n-m+1)$. Because if a hashed number is too small to ...
1
vote
1answer
43 views

Exponential Time Classification

If I have a list of length 'n' where each element is a successive power of 2 would an algorithm that simply prints each element decremented to 1 be classified as exponential time? ...
1
vote
2answers
1k views

What is the difference between Big O and Theta notation in terms of inputs?

In Coreman , it's written : The $O(n^2)$ bound on worst-case running time of insertion sort also applies to its running time on every input. The $\Theta(n^2)$ bound on the worst-case running time ...
3
votes
1answer
79 views

What is complexity class language $L$ such that $\forall\varepsilon > 0,L\in\mathcal{O}(n^\varepsilon)$?

For language $L$, we have $\forall\varepsilon > 0,L\in\mathcal{O}(n^\varepsilon)$. What is the class of $L$? It is obvious that $L\in$ polynomials. Is there a smaller class for $L$? For example, $...
1
vote
1answer
28 views

Does O(f(n)) + O(g(n)) = O(max{f(n), g(n)})?

A question from a lecture of mine. The way I see it, while summing sets is meaningless, O(f(n)) + O(g(n)) is obviously limited from above by the greatest function in either, which means that I ...