Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions about asymptotic notations and analysis

-1
votes
2answers
39 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. ...
-1
votes
0answers
11 views

Verifying complexities of functions [duplicate]

Please confirm following complexities: $$ \log (n^2) = O((\log n)^2)$$ since $\log (n^2) = 2\log n$, which seems to be larger growing function than $\log(\log n)$. $$ n^{1.01} = O(n+100) $$ $$ n^{...
0
votes
0answers
40 views

Assympotic analysis

If we have two functions $f(x)$ and $g(x)$, such that $$\lim_{x\to∞} \frac{f(x)}{g(x)} = c$$ for some finite c, then $f(x) = O(g(x))$. Is the opposite true? That is, if $f(x) = O(g(x))$, must it be ...
1
vote
2answers
28 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
51 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) \\ &\...
1
vote
1answer
14 views

Prove that different definitions of big-Oh with n>=1 or n>N are equivalent

I am coming across two slightly different definitions of big-oh and need to prove that they are equivalent to each other: Definition 1: f(n) = O(g(n)) if there exists constants c and N such that f(n) ...
1
vote
1answer
57 views

Asymptotic Notation Analysis

2^n=O(3^n) : This is true or it is false if n>=0 or if n>=1 since 2^n may or not be element of O(3^n) I need a hint to figure the problem
3
votes
1answer
61 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
57 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
32 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
22 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
49 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(...
2
votes
1answer
22 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
3answers
68 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 ...
1
vote
1answer
30 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
57 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}\...
4
votes
1answer
47 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 ...
2
votes
1answer
119 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
95 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?
4
votes
1answer
457 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
vote
1answer
11 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 \...
0
votes
1answer
34 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 ...
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 \...
3
votes
2answers
37 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) ...
3
votes
1answer
129 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 ...
1
vote
1answer
33 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
3answers
41 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 ...
1
vote
1answer
38 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. ...
1
vote
1answer
19 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
430 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
66 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
25 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 ...
1
vote
1answer
775 views

DFS and BFS Time and Space complexities of 'Number of islands' on Leetcode

Here is the question description. The first 2 suggested solutions involve DFS and BFS. This question refers to the 1st two approaches: DFS and BFS. Apparently, the grid can be viewed as a graph. I ...
0
votes
1answer
28 views

How can I find $\Theta(log(m_1)+…+log(m_k))$ as related to $m$?

given: $$m_1+m_2+...+m_k=m$$ How can I find $\Theta(log(m_1)+...+log(m_k))$ as related to $m$? I know that i can doing that: $O(log(m_1)+...log(m_k))=O(log(m)+...+log(m))=O(k \cdot log(m))$ , but ...
-2
votes
1answer
40 views

Solving double recurrence relation

How to calculate the rate of growth of the below function $f(x)$? $$ \begin{align*} f(x) &= \begin{cases} f(x-1) + g(x) & \text{if } x > 1, \\ 1 & \text{if } x \leq 1. \end{cases} \\ g(...
1
vote
2answers
60 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 ...
3
votes
3answers
221 views

Is there any difference between Time Complexity and Running time?

Is time complexity and running time of the program/algorithm one and the same thing? Also, running time sounds like 'computer complexity'. As, it utilizes all the resources and give tangible time that ...
2
votes
1answer
52 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}{...
1
vote
1answer
25 views

Definition of an Upper Bound

The definition my professor gave us is: f(n) is O(g(n) for constant c > 0 and n0 ≥ 0 where all n ≥ n0 and f(n) ≤ cg(n). I was wondering what n0 and n are? Example: for the function f(n) = an2+ bn + ...
0
votes
3answers
49 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 ...
0
votes
0answers
21 views

Complexity of $T(n) = 4T(n/2) + n^2 \cdot log_2 (n)$ [duplicate]

After constructing the recursion tree i concluded a cost of $n^2\cdot log_2(n)-i\cdot n^2$ per level. So my total cost is: $$\sum_{i=0}^{log_2(n)}n^2\cdot log_2(n)-i\cdot n^2$$ $$=(log_2(n)+1)\cdot ...
-1
votes
2answers
104 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
18 views

Big-O complexity upon taking exponent

If $X \sim \mathcal{O}(\log n)$, then $e^{-X} \sim \mathcal{O} (?)$ Is this a valid question to ask?
-1
votes
1answer
54 views

What will be the computational complexity of a system with two pipelined algorithms?

A system consists of two separate algorithms (operated in pipeline). Algorithm#1 is iterated m times and has a time complexity ...
0
votes
0answers
31 views

I'm having trouble calculating Big O for this bad permutation algorithm

I wrote this code to print all the permutations of a string. I believe it has time complexity of O(N^2). However, I'm not sure about it. Will inner loop run N! times? Can you please help me ...
0
votes
1answer
11 views

What does “order of growth decreases exponentially” mean?

I understand than function decreases exponentially, then order of growth of this function is exponential with negative exponent. But what does it mean that order of growth decreases exponentially? I ...
0
votes
0answers
38 views

Demonstrate that algorithm is O(n)

So i have this algorithm that checks if an binary tree is a binary search tree: ...
1
vote
1answer
132 views

Runtime analysis of while-loop analysis

s = n while (s > 4) s = s / 2 else s = s - 1 Let $T(n) = \Theta(S(n))$ where $S(n)$ is number of while-loop runs. $S(n)=1 + S(n/2)$ if $n$ is even $S(n)=...
0
votes
1answer
67 views

Algorithm Comparison with Theta-notation

We consider two algorithms, Algo1 and Algo2, that solve the same problem. For any input of size n, Algo1 takes time $T_1(n)$ and Algo2 takes time $T_2(n)$. Prove or disprove each of the following ...