Questions tagged [asymptotics]

Questions about asymptotic notations and analysis

Filter by
Sorted by
Tagged with
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 ...
2
votes
1answer
5k 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
30 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
52 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
224 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
1k 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
117 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
108 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
63 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
130 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
21 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
66 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
1answer
16 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 ...
1
vote
1answer
922 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
127 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 ...
1
vote
1answer
47 views

What is the asymptotic time complexity of the following 2 recurrences?

$$T(n) = (\log n) \cdot T(n/\log n) + \Theta(n^i \cdot (\log n)^k)$$ and $$T(n) = (n\log n) \cdot T(n/\log n) + \Theta(n^i \cdot (\log n)^k)$$ for any given $i$ and $k$. I think it helps to know ...
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
0answers
27 views

What is the runtime of Quantum Fourier Sampling

I have seen estimates for the runtime of Shor's Algorithm,, which relies on Quantum Fourier Transformations. What is the runtime of those transformations themselves? Either big-O or more accurate ...
2
votes
1answer
30 views

Complexity Reduction Analysis

I am struggling to grasp fully grasp complexity reductions, I have this example that I am working through and can not fully comprehend how to determine the complexity of one algorithm given the ...
2
votes
1answer
76 views

Big Oh notation for a function with two inputs of linear growth

I'm quite new to time-complexity analysis so I might have misunderstood some basic concepts but lets say we have the following function: ...
2
votes
1answer
349 views

What is the relationship/difference between best/worse/expected case and big O/omega/theta? [duplicate]

In the big O section of Cracking the Coding Interview 6th edition, I read the following. ...
0
votes
0answers
24 views

How to solve recurrence T(n) = 5T(n/5) + n/ lgn [duplicate]

It can't be solved with master method. The result seems to be T(n) = Θ (nlg lgn), but I have a problem to prove it. Could you help please?
2
votes
1answer
89 views

Is $O(|V||E|)$ polynomial time?

If an algorithm runs in $O(|V||E|)$, is its running time bounded by some polynomial of $|V|+|E|$? If not, what is its running time called?
0
votes
1answer
26 views

Proof of big-o propositions

I don't understand the proof of below sentences. $O(f(n))=O(g(n)) \iff \Omega(f(n))=\Omega(g(n)) \iff \theta(f(n))=\theta(g(n))$ $f(n)=\theta(g(n)) \iff g(n)=\theta(f(n))$ How can I prove these ...
2
votes
1answer
167 views

How do you analyse the time complexity of a piecewise function?

Is there a method to apply when trying to finding out the time complexity of a piecewise function? \begin{align*} F(x) &= \begin{cases} 2^x & x < 8, \\ x^2 & x \geq 8. \end{cases} \\ \...
0
votes
0answers
31 views

In what case would bi-directional BFS have the same asymptotic run time as a regular BFS?

I'm not quite sure when they would have the same asymptotic running time. Would it be if the graph was each node connected to one other node in a line? I know that for a bi-directional BFS to have a ...
2
votes
1answer
193 views

Is the worst-case of this algorithm equal to $\Theta(n)$ or $\Theta(n\lg n)$?

I am trying to find the worst-case complexity of the following algorithm. The input to the algorithm is a list of positive integers $a_1,\ldots,a_n$ and a bound $C$. $S\gets$ empty set $k\gets0$ for $...
3
votes
1answer
241 views

Minimal date interval cover algorithm

The problem involves date intervals filtered by days of week. For example, the filtered interval {2001 APR 1 - 2001 APR 30, 17} corresponds to all Mondays and Sundays between April 1 and April 30. ...
0
votes
2answers
219 views

Two questions about complexity class

Does $2^{n-1}$ and $2^{n}$ share the same complexity complexity class as exponential named as $O(2^n)$? So the former belongs to $O(2^n)$ even though it's one order lower? What is the name of the ...
3
votes
1answer
40 views

Is $T(n) = Ω (n^2)$ the same as $n^2=O(T(n))$?

Question: In the problem below, does proving $T(n) = O(n^2)$ and $n^2 = O(T(n))$ lead to the same result as proving $T(n)=O(n^2)$ and $T(n)=Ω (n^2)$? Which would be the better approach to take? I feel ...
0
votes
0answers
11 views

Show that x^3 + 5x is not O(x^2) [duplicate]

Below is my solution. Is this sufficient enough to prove? $$|x^3+5x| \le |x^3+5x^3|$$ $$x^3 + 5^x \le 6x^3, x > 1, C=6$$ Let's take $x = 2$. $$f(x) = (2)^3 + 5(2) = 18$$ $$g(x) = 6\cdot 8 = 48$...
1
vote
1answer
142 views

Understanding time complexity of a while loop that will look over all vertices and edges

I need a little clarification on differing time complexities. My analysis for the below algorithm was $O(n +nm)$, but the correct analysis would be $O(n+m)$. I know that ...
2
votes
1answer
113 views

Time Complexity of a Union Find algorithm

I'm trying to understand the time complexity of an example algorithm. My conclusion was O(n^2) but this was considered wrong. The algorithm is as follows: input: data: array of sorted n integers input:...
-2
votes
1answer
61 views

What is $\sum_{k=1}^\infty \frac{1}{k^2 H_k}$?

According to this answer, $\sum_{k=1}^\infty \frac{1}{k^2 H_k}$ is approximately 1.33275. How?
1
vote
1answer
63 views

Big O of an algorithm that relies on convergence

I'm wondering if its possible to express the time complexity of an algorithm that relies on convergence using Big $O$ notation. Is it fair to say that we can't reason about an algorithm's scalability ...
1
vote
2answers
56 views

Finding Big O of 1/n + 1/n+2 … 1/n'

The number of computations of an algorithm is $n'm\sum_{x=0}^{n'-m} 1/(m+x)$. What is the complexity of the algorithm ? Thanx for help.
0
votes
0answers
99 views

If $f(n)=\omega(h(n))$ and $g(n)=o(h(n))$ then is $f(n)=\Theta(g(n))$?

My question is exactly what the title says. If I have that $f(n)=\omega(h(n))$ and $g(n)=o(h(n))$ hold, then does $f(n)=\Theta(g(n))$ hold as well? My intuition says that the second part is false, but ...
0
votes
0answers
202 views

How to find lower bound of f(n) for master theorem

I'm studying the master method to solving a recurrence. It describes three cases, the last one of which depends on what lower bound a function f(n) has. I usually ...
1
vote
1answer
64 views

how can i proof $3^n$ has a greater growth than $n2^n$? [duplicate]

i want to prove that $3^n$ has a greater growth than $n2^n$ or $3^n = O(n2^n)$. but how can i do it mathematically? by induction or contradiction or other ways of proof.
0
votes
1answer
86 views

Big O understanding given different input sizes

I have a question about big O notation. Let's say I have 3 algorithms which, for an input of size $n$, have time complexity $O(n)$, $O(n^2)$ and $O(n \log n)$, respectively. Assume that all 3 ...
0
votes
2answers
49 views

Is every algorithm on bounded resources O(1)

Suppose that I have a restricted Turing Machine - it has finite tape and takes bounded input. Consider a program that halts on every input (which is at most $k$ bits). The set of inputs is finite, ...
0
votes
0answers
91 views

Big O Notation for Return List is it O(N)?

what is the Big O for Returning List? aka return list (e.g. list=[1,2,...]) is it o(1) or o(n) and is there a good website for average big o for different operations including sorting for simple ...
1
vote
0answers
49 views

Can there be functions in o(1) in algorithm analysis?

I saw a similar question to this one here but it's not quite the same as mine: Is every algorithm's complexity $\Omega(1)$ and $O(\infty)$? I've just started a course in data structures and ...
1
vote
1answer
27 views

How to prove that $n^d$ is $O(b^n)$ from $n$ is $O(2^n)$, given that $d>0, b>1$? [duplicate]

I'm reading Rosen's Discrete Mathematics and Its Application, at Page 212, it's about the "Big-O" notation using in computer science. This is the description in the book: And here is my reasoning: ...
-1
votes
1answer
61 views

Algorithms - In which relation to the big O notation are the functions lg n and ln n? [duplicate]

I want to prove in which relation the two functions stand to each other with the help of a proof. But how?
-1
votes
2answers
91 views

Big-O notation analysis [duplicate]

Can I get help to give an analysis of the running time Big-O? I'm not sure if all my answers are correct. I got for a) $ O(n)$, b) $O(n^3)$, c) $O(n^{1/2})$ and d) $O(log(n))$ ...
0
votes
2answers
56 views

Calculate the Time complexity

$T(n)=\sqrt{2T(n-1)}$ what will be the time complexity if $T(n)$ is given as this? I tried substitution but no result was reached.
0
votes
1answer
37 views

Determining the complexity of calculating n-th root of an integer, and performing modulo arithmetic?

For a while now, I have been struggling to find a source explaining the complexity of the following 2 elementary operations Calculating the $n^\text{th}$ root of an integer $x$, $$ \sqrt[\leftroot{-3}...
4
votes
2answers
84 views

If $f(n)$ is $O(g(n))$ is it also $O(g(n-d))$?

When trying to prove that a recurrence $g(n)$ satisfies $g(n) = O(f(n))$, we sometimes are not able to find a valid $C$ to show the upper bound, so we try to prove it is $O(f(n-d))$ for some constant $...