Questions tagged [asymptotics]

Questions about asymptotic notations and analysis

Filter by
Sorted by
Tagged with
-1
votes
1answer
29 views

Is $\sum_{i=1}^n i \in \Theta(n^2)$?

Please help me understand on how to prove or disprove the following. I have been practicing and doing others which are ok, but with this sum, it is rather confusing. $$\sum_{i=1}^n i \in \Theta(n^2)...
0
votes
0answers
28 views

Can the average case of an algorithm be $O(n \log n)$ if the best case running time of an algorithm is $\Theta(n \log n)$? [duplicate]

Let us suppose the best case running time of an algorithm is $\Theta(n \log n)$. Can the average case run time of the algorithm be $O(n \log n)$? Since $O(n\log n)$ would imply the value going even ...
0
votes
2answers
84 views

Showing that $\lg(n!)$ is or is not $o(\lg(n^n))$ and $\omega(\lg(n^n))$

My instructor assigned a problem that asks us to determine which asymptotic bounds apply to a certain $f(n)$ for a certain $g(n)$, in my case $f(n) = \lg(n!)$ and $g(n) = \lg(n^n)$. For clarity, the ...
1
vote
1answer
57 views

Solving the recurrence $T(n) = n^{3/4}𝑇(𝑛^{1/4})+ n $

I need to solve the following recurrence relation: $T(n) = n^{3/4}𝑇(𝑛^{1/4})+ n $. Obviously, the master theorem doesn't apply here so I was using the substitution method. I used $x=\log n$ and $F(x)...
1
vote
1answer
15 views

Algorithm notation between two functions [duplicate]

I have two functions, $$ f = n^{1.6} $$ $$ g = n^{1.5} $$ I thought this is $ f=\theta(g) $, since $ f $ is asymptotically tight bound of $ g $, if $ n $ goes to infinity. However, the answer is $ f ...
2
votes
1answer
114 views

All pair shortest path in a tripartite graph

I have a tri-partite graph with three sets of vertices source, bridge and destination nodes. I want to find the shortest path between every vertex in the source set to every vertex in the destination ...
0
votes
1answer
119 views

What time complexity (big o) is this specific web crawler implementation?

Note: this question was marked as a duplicate in favor of this question/answer which attempts to provide a generic formula for translating code to mathematics. Unfortunately I didn't find that ...
7
votes
2answers
713 views

The recursion $T(n) = T(n/2)+T(n/3)+n$

I'm looking at the reccurrence $$T(n) = T(n/2) + T(n/3) + n,$$ which describes the running time of some unspecified algorithm (base cases are not supplied). Using induction, I found that $T(n) = O(n\...
1
vote
0answers
34 views

Prove that the upper bound for T(n)=T(an)+T(bn)+O(n) is O(n) [duplicate]

While learning Median of Medians algorithm i came across the following lemma ; "For any recurrence of the form $T(n)<=T(an)+T(bn)+O(n) $, if $(a+b)<1$ the reccurence will solve to $O(n)$" (...
2
votes
1answer
40 views

Solving T(n) = T(n-1)*T(n-2)

So, this is how I solved $\displaystyle T(n-1) \approx{} T(n-2) $ $\displaystyle T(n) = T(n-1)^2 $ Add log in both sides $\displaystyle log(T(n)) = 2log(T(n-1)) ...
1
vote
2answers
679 views

Does converting adjacency matrix representation of graph of size $n \times n$ to adjacency list always require $O(n^2)$ time?

Assume that I have the adjacency matrix representation of a graph in $0,1$ values. Does converting it to a corresponding adjacency list representation always have a time complexity of $O(n^2)$?
5
votes
1answer
174 views

Why integer division is of equal complexity as multiplication

I am trying to understand the fact that integer division is no more difficult than integer multiplication. I found some references - here and this lecture note. Wikipedia says if there is a way to ...
-1
votes
1answer
104 views

Analyzing asymptotic notation $\sqrt n = O(\log^2 n)$

I am trying to determine whether $f(n) = \sqrt n$ is in $O(g(n))$, $\Omega(g(n))$, or $\Theta(g(n))$ where $g(n) = \log^2 n$. The answer says that only $f(n) = \Omega(g(n))$ is correct, but why isn't ...
0
votes
3answers
166 views

What is the asymptotic complexity of the following code snippet?

for (i = 2; i < n; i = i * i) { for (j = 1; j < i / 2; j = j + 1) { sum = sum + 1; } } I know that the outer loop can run for a maximum of $n^2$ ...
1
vote
1answer
41 views

Asymptotic relation between n! and (n+1)!

I am having difficulty writing this formally. I know that by L'Hospital's rule we can reduce it to $\lim_{n \to \infty} \frac{n+1}{n}$ which is a constant and hence $n = \theta (n+1)!$. But I am not ...
1
vote
1answer
79 views

Master Method: $T(n) = 10T\Big(\frac{n}{2}\Big) + \frac{n^4}{\log(n)}$

I'm having a hard time trying to understand how to solve this recurrence relation using the Master Method: $$T(n) = 10T\Big(\frac{n}{2}\Big) + \frac{n^4}{\log(n)}$$ First, we have: $a = 10,\ b = 2$ ...
0
votes
1answer
27 views

Algorithm comparison

I am learning Big O and Big theta notation and confused the certain case. I have two functions, function 1(f1) $$ n * n^{1/2} $$ function 2(f2) $$ 1.001^n $$ in smaller cases (10,000) f1 is much ...
0
votes
0answers
29 views

The applicability of the Master Theorem and calculation of asymptotic limits

Given the following recursive equation $T(n)=3T(\dfrac{n}{8})+ Θ(n^{1/3})$ I want to know how to explain the applicability of the Master theorem in a rigorous way and what means asymtotic limits of ...
2
votes
2answers
73 views

Meaning of $ e^x = 1 + x + Θ(x^2)$?

In the CLRS chapter 3: When $x → 0$, the approximation of $e^x$ by $1+x$ is quite good: $$e^x = 1 + x + Θ(x^2).$$ How is it to be interpreted, what is the role of asymptotic notation here?
1
vote
2answers
142 views

Running Time of Sorting Algorithm

Determine the asymptotic running time of the sorting algorithm maxSort. Algorithm maxSort(A) Input: An integer array A Output: Array A sorted in non-decreasing order ...
7
votes
4answers
231 views

What is the depth of recursion if we split an array into $\log_2(n)$ with each recursive call?

We have a function which takes an array as input. It breaks an array into $\log_2(n)$ parts with equal sizes where $n$ is the size of the subarray. It keeps breaking each of the subarrays until there ...
1
vote
1answer
48 views

Are the following Big Oh Notations equivalent?

In the context of Upper bounds computaion and Big Oh Notation, I was wondering if the following could be proved... if they are equivalent. $\mathcal{O}((log(n))^{-1}) = (\mathcal{O}(log(n)))^{-1}$ $\...
3
votes
2answers
205 views

$f(n) = o(n^c) \rightarrow \exists \epsilon > 0 \ s.t. f(n) = O(n^{c-\epsilon})$

I'm trying to prove that for arbitrary $c > 0$, $f(n) = o(n^c) \rightarrow \exists \epsilon > 0 \ s.t. f(n) = O(n^{c-\epsilon})$ Intuitively, this seems to be true to me (little-o implies ...
2
votes
1answer
250 views

Running Time for Finding Maximum

Consider the algorithm findMax that finds the maximum entry in an integer array. Algorithm findMax($A$) Input: An integer array $A$ Output: The maximum entry of $A$ ...
0
votes
2answers
1k views

How to calculate time complexity of a randomized search algorithm?

Example: Finding an element from a sorted array Let's say we have an algorithm that accepts a sorted array of length N as its input. Then in each iteration it randomly selects an element from the ...
1
vote
1answer
18 views

Bounds on “well dispersed” sparse matrices

Suppose we have an $n\times n$ zero/one matrix $M$, with $k$ ones. Let us say that the extent of $M$ is the maximum of $i+j$ over all ones at positions $(i,j)$ of the matrix, and the quality $q(M)$ is ...
3
votes
1answer
127 views

Performance of Modified Dijkstra's algorithm with Binariy heap as Priority Queue

we know the performance of Dijkstra's algorithm with binary heap is O(log |V |) for delete_min, O(log |V |) for insert/ decrease_key, so the overall run time is O((|V|+|E|)log|V|). Now let's modify ...
0
votes
2answers
57 views

Terminology for worst-case N-complexity on $O(1)$ insert after amortisation

Normally, when discussing amortisation and worst-case complexity, amortisation negates the worst-case scenarios, and the BigO describes the average for the operation (the way it's used in interviews ...
2
votes
2answers
112 views

Are Big-Theta functions asymptotic monotonically non decreasing?

For example, suppose $f(n) = \Theta(n^2)$, then does that mean for any sufficiently large $n$, $f(n) \le f(n+1)$? Is it a general case for all Big-Theta?
1
vote
2answers
60 views

Is $f(cn)$ always $O(f(n))$ for constant $c$ and any function $f$?

This seems to be true for any function I can think of, but I'm not quite sure how to prove it. Is there a proof of this proposition for any such function or a counter-example?
2
votes
1answer
106 views

What is the Big-Ω of the following function?

For the following function: $$ \sum_{n=1}^{2n}x+x^2 $$ It is easy to see the (tightest) Big-Oh is $O(n^3)$, but I am not so sure about the Big-Omega. Here is my attempt: $$ \sum_{n=1}^{2n}x+x^2 $$ $...
3
votes
1answer
204 views

d-ary heap implementation vs Fibonacci heap implementation Dijkstra performance comparions

Let's say that Dijkstra’s algorithm with the priority queue using a d-ary heap. if adjusting d, we can try to achieve the best runtimes for the algorithm with d being $\sim |E|/|V|$. Then for a ...
4
votes
2answers
112 views

When is this even possible (even for a dense graphs) $|E| = \Theta (|V|^2)$

Wikipedia says that "a dense graph is a graph in which the number of edges is close to the maximal number of edges." and "The maximum number of edges for an undirected graph is $|V|(|V|-1)/2$". Then ...
0
votes
0answers
23 views

Run time analysis of inner loop [duplicate]

What is the run time of the following piece of code in Big-Oh notation? The first loop runs n times in the worst case. But I am having difficulty in finding run time of nested loop which runs V / deno[...
0
votes
0answers
15 views

Runtime explanation of this function [duplicate]

I am trying to understand the runtime complexity of the below code in terms of n. I know that it is $Θ(n^{4/3})$, but I don't get why. I thought the outer loop runs $log(n)$ times, the second one ...
1
vote
1answer
96 views

Is $O(T+\log T)= O(T\log T)$?

Is $O(T+\log T)= O(T\log T)$? I think this is true but I do not know how to show it mathematically? Please show it using the definition. Also, if it is true, is the following true? $O((T+\log T)^{...
1
vote
1answer
139 views

Missing part of the proof of Master Theorem's case 2 (with ceilings and floors) in CLRS?

I am trying to go through the proof of the Master Theorem in Introduction to Algorithms of Cormen, Leiserson, Rivest, Stein (CLRS). The theorem providers an asymptotic analysis for recurrence ...
1
vote
1answer
74 views

Why $2R\sigma\sqrt{T+logT+1}=\tilde{{O}}(\sigma\sqrt{T})$?

On page 17 on the paper Online Learning with Predictable Sequences, we find a regret of an algorithm equal to $$ \text{Reg}_T=\frac{R^2}{\eta}+\frac{\eta}{2}\sigma^2(T+logT+1) $$ where $T$ is the ...
2
votes
1answer
52 views

Can I say the two cases of Recursion Tree are always either $\theta{(n)}$ or $\theta({n\log{n}})$

Given positive constants: $c_1, c_2, ..., c_k, c^\prime$, assume that $T(n) = T(c_1n) + T(c_2n) + ...+ T(c_kn) + c^\prime n$ There are two cases: $c_1 + c_2 + ...+ c_k < 1$ $c_1 + c_2 + ...+ c_k ...
2
votes
3answers
812 views

How to properly calculate dependent nested loops for big-O [duplicate]

I am revising for my algorithms exam and I have come across one topic in particular that I do not quite understand; which is how to analyse dependent nested loops. I know if we have a 2-nested loop, ...
1
vote
2answers
1k views

Show that for any real constants $a$ and $b$, where $b > 0$, $(n + a)^b = \Theta(n^b)$

I'm currently studying growth of function chapter in Introduction to Algorithm. In exercise 3.1-2 the question is: Show that for any real constants $a$ and $b$, where $b>0$, $(n + a)^b = \...
0
votes
1answer
25 views

Big O analysis trying to follow a logic

Can someone please help me understand why(the derivation) "and m = 2n+1 for each n."? I am trying to follow the logic of the solution provide while myself have a different approach. Here is my ...
0
votes
1answer
179 views

Let $f(n)=\Omega(n), g(n)=O(n)$ and $h(n)=\theta(n)$ then $f(n).g(n)+h(n)$ is?

Let $f(n)=\Omega(n), g(n)=O(n)$ and $h(n)=\theta(n)$ then $f(n).g(n)+h(n)$ is? My attempt: Lets $f(n)=g(n)=n$, then $f(n).g(n)+h(n)=\Omega(n^2)+\theta(n)=\Omega(n^2)$ But given answer is $O(n)$. ...
47
votes
10answers
11k views

O(·) is not a function, so how can a function be equal to it?

I totally understand what big $O$ notation means. My issue is when we say $T(n)=O(f(n))$ , where $T(n)$ is running time of an algorithm on input of size $n$. I understand semantics of it. But $T(n)$ ...
0
votes
1answer
2k views

How come O(n) + O(logn) = O(logn)

How come O(n) + O(logn) = O(logn)? When talking for example about an algorithm that has two operations. One of them takes O(n) and the other O(logn) and in the end we say that the total complexity is ...
0
votes
1answer
50 views

Is this a valid use of big-O notation?

Suppose that $m=O(n^{c+1/2})$ for some real $c>0$ and $x=O(\sqrt{\log m})$. Are the following two computations valid? I understand that I'm abusing notations a bit to get at the desired results. ...
1
vote
1answer
71 views

What is the solution of $T(n, m) = T(n, m-1) + T(n-1, m) + c$?

Consider the recurrence $$ T(n,m) = T(n,m-1) + T(n-1,m) + c, $$ with base cases $T(n,0) = T(0,m) = 1$. This is the complexity of a recursive algorithm for the longest common subsequence, I know that ...
1
vote
2answers
178 views

How to compute the complexity of $T(n) = T(n-2)+T(n-3)+2T(n/3)$?

$T(n) = T(n-2)+T(n-3)+2T(n/3)$ and $T(n)=1$ for $n<4$. I tried to compute the complexity of $T(n) = T(n-2)+T(n-3)+2T(n/3)$ using the recursion tree but it's not clear enough for me to make a guess ...
1
vote
1answer
149 views

Big O space complexity of this isAnagram method

I'm currently debating with some friends what is the Big O space complexity of this isAnagram method: ...
1
vote
1answer
57 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 ...

1
3 4
5
6 7
22