Questions tagged [asymptotics]
Questions about asymptotic notations and analysis
1
vote
2answers
46 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)$?
4
votes
1answer
42 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
45 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
0answers
12 views
Algorithm to find sum of all values in a 2D matrix when i<j [closed]
Given an array A of n integers, output an n by n array B in which B[i,j] (for all i=j values of B[i,j] are left unspecified so ignore that case).
My approach:
The most natural way to do this is by ...
0
votes
1answer
22 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
36 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
27 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
25 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
20 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
65 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?
0
votes
0answers
34 views
Big Oh/Omega/Theta Notations [duplicate]
I am trying to learn Asymptotic notations from the famous Algorithms, Dasgupta,Vazirani book. I found some exercises at the end of the chapter, which I have attempted to solve, but I am not sure if I ...
1
vote
2answers
49 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
104 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
37 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
121 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 ...
1
vote
1answer
55 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
45 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
votes
0answers
27 views
Are Θ,Ο,Ω, etc. considered functions of function? [duplicate]
Are Θ,Ο,Ω, etc. considered functions of function? Or just sets of function?
1
vote
1answer
11 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
65 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
37 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
34 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
53 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
102 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
104 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
74 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
10 views
forming recurrence equations from code [closed]
Please could someone help me with understanding how to form recurrence equations when reading code? I'm having some trouble in my class:
...
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
46 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
44 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
61 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
46 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
82 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
87 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
22 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
50 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)$. ...
44
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
66 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
45 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
65 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
77 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
72 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
46 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 ...
4
votes
2answers
145 views
Is “super-exponential” a precise definition of algorithmic complexity?
I cannot seem to find a precise definition of what "super-exponential" is supposed to refer to when one's talking about an algorithm's time complexity.
For instance, if an algorithm runs for $nC(n-1)$...
0
votes
1answer
22 views
Showing $2^x$ is a lower bound
How do I show that $2^x - x^2 \in \Omega(2^x)$?
Basically, I know that this means that $\exists a, x_0 \in \mathbb{R^+}, \forall x \in \mathbb{N}, a.2^x \leq 2^x - x^2$.
I worked around a bit with ...
0
votes
1answer
22 views
Big O order of a function
I'm doing some practice questions on Big O notation and came across this question. What is the Big O order of function 𝑓(𝑛) = 𝑛^2 + 𝑛 log2(𝑛) + log2(𝑛). Show your working.
My answer is O(n^2) ...
1
vote
1answer
44 views
How to find sets of polynomially bounded numbers whose subset sums are different?
Let $n$ be any positibe integer and set $N=\{1,\dots,n\}$. Now select two arbitrary but different subsets of $N$, say $S$ and $S'$. We are interested in finding a function $\pi(A)=\sum_{i\in A}a_i$ ...
1
vote
2answers
65 views
Is the runtime of binary search big omega of logarithm of n?
My question is that can we say that runtime of the binary search is $\Omega(\log n)$?
I know it is both $\Omega(1)$ and $O(1)$ for the best case, and $\Omega(\log n)$ and $O(\log n)$ for the worst ...
1
vote
1answer
49 views
Big O and constants [duplicate]
I've already asked this question on stack overflow, but guys have suggested me to ask my question here.
Let's consider classic big O notation definition (proof link):
The $O(f(n))$ is the set of all ...
