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 tagged [asymptotics]

Questions about asymptotic notations and analysis

0
votes
2answers
36 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
31 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
52 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
100 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
98 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
67 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
9 views

forming recurrence equations from code

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
37 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
57 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
72 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
21 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
49 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)$. ...
43
votes
10answers
10k 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
0answers
29 views

Lower bound of an iterative algorithm involving a while loop

I have an algorithm that includes a while loop (plus some preceding and subsequent steps that are each run only once). The least number of iterations required for my algorithm to converge is 1. ...
0
votes
1answer
61 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
71 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
62 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 ...
0
votes
0answers
24 views

Solving Recurrence relation using Master Theorem

There is a recurrence relation like $T(n)=mT(n/2)+cn^2$ To solve this recurrence relation I am using Master Theorem. As per master theorem here a = m, b = 2, k=2 ,p=0 So $b^k= 2^2 = 4$ Now, ...
-1
votes
0answers
45 views

What's the lower bound of the height of an unbalanced recursion tree?

I don't understand what's going on here. People say, longest path should yield an upper bound of tree height while shortest path should yield a lower bound of tree height. Please take a look at https:/...
4
votes
2answers
110 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
43 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
54 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
48 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 ...
0
votes
2answers
31 views

Calculation of Inorder Traversal Complexity

I want to analyze complexity of traversing a BST. I directly thought that its complexity as $O(2^n)$ because there are two recursive cases. I mean $T(n) = constants + 2T(n-1)$. However, AFAI research ...
1
vote
1answer
23 views

Big-Oh vs Theta in recurrence tree method

I am solving this problem from here. The given relation is $$T(n) = 2 T(\frac{n}{2}) + n^2, \, T(1) = 1$$ The solution via recurrence tree method is given as: The zeroth level has a single node ...
1
vote
1answer
61 views

Asymptotic behavior of $n\sqrt n + n \log n$ & $\log_{100} n$ [duplicate]

I have the following two functions $f(n) = n\sqrt n + n \log n$ $\log_{100} n$ And I need to classify them into the followings: $O(n)$, and/or $O(n^2)$, and/or $O(n^3)$, and/or $O(n^{1.5})$, and/or ...
1
vote
2answers
56 views

Big-O Solving Recurrence Relation by iteration with fractions

I was trying to solve the recurrence relation in order to get a some big-O bound $$ B(n) = B(n-4) + \frac{1}{n} + \frac{5}{n^{2} + 6} + \frac{7n^{2}}{3n^{3} + 8}$$ by following the accepted answer ...
1
vote
2answers
80 views

Why is $\dfrac{1}{2}n^2-3n = \Theta(n^2)$?

By definition: For a given function $g(n)$ we denote by $\Theta(g(n))$ the set functions $\Theta(g(n))$ = $\{f(n):$ there exists positive constants $c_1, c_2$ and $n_0$ such that $0 \leq c_1g(...
0
votes
0answers
24 views

Does $\lg{(n+1)} \in O(\lg{n})$? [duplicate]

I know this is kind of an ugly notation, so if you prefer: let $f(n) := \lg{(n+1)}$. Does it hold that $f(n) \in O(\lg{n})$?
3
votes
2answers
56 views

Asymptotic growth of $\log(n^n + n)$

I would like to know if my understanding of this is correct: The question asks to show that the Big-Oh of the following function is $O(n\log(n))$ $$ \log(n^n + n) $$ I think the first step is to ...
3
votes
3answers
116 views

How can I solve the recurrence $T(n) = 4T(n/2) + n^2\log^2n$? (without master theorem) [duplicate]

I can not find the appropriate variable to change the second part $n^2\mathrm{log}^2n$.
0
votes
1answer
28 views

Why is max{n,k}= Ө(n+k) [duplicate]

I saw this relationship in my exercise. max{n,k}= Ө(n+k) Could somebody prove it?
1
vote
2answers
48 views

Is $n^3$ an asymtotically tight bound of $(n^{2.99}).(\log_2n)$? How? [duplicate]

Is $n^3$ an asymtotically tight bound of $(n^{2.99}).(\log_2n)$? If so then how?
1
vote
1answer
17 views

Represent polynomial time complexity as linearythmic

To determine the experimental time complexity of radix sort, I wrote a program that counted the number of steps the algorithm took to sort N points. I ran that program for multiple N length arrays, ...
0
votes
1answer
62 views

Show that $T(2^n) = \Theta(3^n)$ [duplicate]

We have a function $T(n)$ defined by $T(1) =1$ and $T(n)=3T(\lfloor n/2\rfloor)+n$ for $n > 1$. We need to show that $T(2^n)=\Theta (3^n)$. How should I approach this question? Any suggestion?
0
votes
1answer
69 views

Big O Notation Simplification in the fraction form

How should I approach this one a(n) = $\frac{n^3}{log^{3}(n)}$. As We can tell that $n^3$ grow much faster than $log^{3}(3)$. All of sudden, not sure what to do, found this [post][1], which is also ...
1
vote
1answer
126 views

Big-O with nested loops and “variables” in the T(n)

So, I need to find the T(n) and then Big-O (tight upper bound) for the following piece of code: ...
1
vote
1answer
60 views

Introductory explanation of the Big-Oh properties

I've noticed that Big-Oh notation actually has some properties such as summation, product but i couldn't find an introductory explanation for their use or how they can help to solve asymptotic ...
1
vote
2answers
46 views

How to prove $\Theta(g(n))\cup o(g(n))\ne O(g(n))$

How to prove $\Theta(g(n))\cup o(g(n))\ne O(g(n))$ ? Is there a simple example for understanding? Seems there's a gap between $O(g(n))- \Theta(g(n))$ and $o(g(n))$ just from the definition. But I ...
1
vote
1answer
23 views

Is this correct in term of big-oh notation: given $g = O(f)$ and $h = O(f)$ can we say $g = O(h)$?

We have two equations $g = O(f)$ and $h = O(f)$ , then can we derive that $g = O(h)$. I came up with following proof but i dont know it's correct or not. $$g = O(f)$$ $$g \le c_1*f $$ $$h \le c_2*f $$ ...