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 ...
