Questions tagged [asymptotics]

Questions about asymptotic notations and analysis

Filter by
Sorted by
Tagged with
2 votes
1 answer
381 views

Asymptotics of the sum of a geometric series

I have a parameter $q$ which is the probability of selecting a vertex (among $n$ vertices...) to be in a certain set. I am constructing the sets in an iterative way, having the vertex $v_i$ be in the ...
V. Prasad's user avatar
  • 125
1 vote
1 answer
64 views

Sorting rational numbers in linear time

I am currently studying algorithms and computational complexity at University. I have recently got through three questions I found in an old exam: Is it possible to sort in asymptotically linear time ...
Lorenzo's user avatar
  • 11
1 vote
1 answer
56 views

Show if $f(n)$ has polynomial growth and $g(n)=\Theta(f(n))$, then $g(n)$ also has polynomial growth

As stated in the question title, if $f(n)$ has polynomial growth and $g(n)=\Theta(f(n))$, then how can we show $g(n)$ also has polynomial growth? $g(n)=\Theta(f(n))$ gives us $0\leq c_1f(n)\leq g(n)\...
Mason Rashford's user avatar
0 votes
1 answer
34 views

How are pointers modeled on bit-based computer models?

Why bit-based computer models? The perhaps most commonly used computer model is a random access machine that can store natural (or even real) numbers in infinitely many cells indexed by natural ...
KGM's user avatar
  • 103
0 votes
1 answer
34 views

find $f(n)$ for recurrence $T(n)=2T(\dfrac{n}{2})+\mathcal{O}(n\log{n})=\Theta(f(n))$

We have recurrence $T(n)=2T(\dfrac{n}{2})+\mathcal{O}(n\log{n})$ and assume $T(1)$ is a constant. Find asymptotically tight bounds $\Theta(f(n))$ for $T(n)$. There's something that confuses me. We ...
Mason Rashford's user avatar
0 votes
1 answer
55 views

Find time complexity of $T(n)=3T(n-2)+O(n)$

I try to find the time complexity of following recurrence relation: $$T(n) = 3T(n-2) + O(n)$$ After subtitution,I get: $$T(n)=3^{\frac{n}{2}}T(0)+\sum_{i=0}^{\frac{n}{2}-1}3^iO(n-2i)$$ I wonder if the ...
Ash丶Dr's user avatar
1 vote
0 answers
23 views

Upper bound via standard manipulation in proof of semi-private learning

I have been reading a paper on private learning [1]. In the proof of lemma 3.3. they claim that $$ 2\left(\frac{2e n_\text{pub}}{d}\right)^{2d}e^{-\alpha n_\text{pub}/4} $$ is upper bounded by $\beta$ ...
TheCollegeStudent's user avatar
0 votes
1 answer
46 views

Why, for $f(n) = n \cdot \sqrt n$ and $g(n)=n(\log n)^5$, we have $f = \omega(g)$? log is base 2

Could you please explain me why that's the case?
user avatar
0 votes
0 answers
18 views

Time complexity summations

How to calculate the time complexity of a algorithm which contains while loops or if statements using summations? I only know how they work with the for loops. And I'm guessing the if loop are ...
Ninaaaaa's user avatar
0 votes
1 answer
34 views

Which one grows faster, an exponential function where the exponent grows faster than logarithmic or a factorial powered by n?

Which function grows faster: $$f(n) = 4^{n^2 \log_2 n} \text{ or } g(n) = (n!)^n$$ Which is true? $f(n) = O(g(n))$ $g(n) = O(f(n))$ i.e., $f(n) = \Theta(g(n))$ none of the above? For lower values of ...
Kong's user avatar
  • 1
0 votes
1 answer
35 views

Proving asymptotic classes

I am trying to teach myself asymptotic notations. I feel like I'm in over my head. I read the explanations in the text book, and Khan Academy. But when I try to do proofs, I can't grasp anything. I'm ...
Jane's user avatar
  • 1
0 votes
1 answer
65 views

Asymptotic equivalence allows difference by a constant factor?

Wikipedia and other sources define "asymptotically equivalent" as: two functions $f$ and $g$ are asymptotically equivalent if: $$ \lim\limits_{x \to\infty}\frac{f(x)}{g(x)}=1 $$ But we ...
Kardashev Type V's user avatar
0 votes
2 answers
48 views

From these functions, how to determine which grows faster without graphing?

How are you intuitively able to tell the Big-Oh of the functions and what order they are on? $$f(n)=3^n$$ $$g(n)=5^{3log_3{n}}$$ Note this is $5$ raised to $3log_3n$ $$h(n)=1024^{log_2n}$$
Stewart Jean's user avatar
1 vote
3 answers
97 views

Is $n^{1.03} = \Omega(n \log \log n)$?

We had this problem on our Algorithms final. It threw me off because if $\log$ is $\log_2$ then graphing the function shows this is not true, but if $\log$ is $\log_{10}$ then it looks like it is. How ...
pod's user avatar
  • 117
-1 votes
3 answers
55 views

Can anyone help explain why the time complexity for this is O(n)

So ive already tried lookig at it but i just get O(nlogn) which is not correct there were some clues like using a geometric series where 1/2+2/4+3/8+i/2^i<2 but idk how to implement that what ...
Guest's user avatar
  • 1
0 votes
2 answers
65 views

Subtracting Two same asymptotic values

I am dealing with two values $a$ and $b$ such that they grow at the same asymptotic rate, i.e., $O(\frac{1}{\sqrt{N}})$. I want to achieve a reasonable bound for the difference $a - b$. When I go into ...
Zeeshan ahmed's user avatar
-1 votes
2 answers
69 views

Finding asymptotically tight upper bound of a recursion relation

Find an asymptotic tight upper bound for the following recursion relation: $$T(n)=5T(\frac{n}{5})+\log^2(n)$$ I tried to solve it by applying iteration: $$T(n)=5T(\frac{n}{5})+\log^2(n)=5(5T(\frac{n}{...
GBA's user avatar
  • 99
2 votes
6 answers
1k views

Assuming constant operation cost, are we guaranteed that computational complexity calculated from high level code is "correct"?

Edit: Since this post is gaining traction, I feel the need to clarify that the purpose of this is to see if asymptotic and constant factor estimations calculated from high level code implementations ...
wjmccann's user avatar
  • 549
-1 votes
1 answer
45 views

Solve Recurrence Equation: 𝑇(𝑛)=𝑇(𝑛−4)+𝑛^2

I'm trying to practice recurrence equations, so I'm trying to solve this typology by unfolding method. I was wondering if what I write below was correct and obviously the result: $T(n) = n^2 + T(n-4) =...
emacos's user avatar
  • 121
0 votes
0 answers
6 views

Asymptotics Accounting for Invocation Frequency in the Context of the broader system

I did some thinking and analysis this evening and I'm wondering if what I'm pointing out here is interesting: https://medium.com/@nwcodex/invocation-asymptotics-runtime-cost-based-on-the-anticipated-...
user161310's user avatar
0 votes
2 answers
168 views

When does Quicksort go from O(n log n) to O(n^2)?

Quicksort is O(n log n) average case, and O(n^2) worst case. The worst case occurs if one side of the pivot contains all of the elements and the other side contains none. However, I think the worst ...
TheSwiftTiger's user avatar
0 votes
0 answers
34 views

Shell sort algorithm analysis

Given this Shell sorting algorithm implementation: ...
Kim's user avatar
  • 1
0 votes
0 answers
23 views

Shell algorithm knuth sequence time complexity analysis

Given this shell sort algorithm implementation: ...
Kim's user avatar
  • 1
1 vote
0 answers
17 views

Complexity of m bit multiplication & division [duplicate]

In PRIMES IS IN P paper, page 6 under Time Complexity section, authors have mentioned "In these calculations we use the fact that addition, multiplication, and division operations between two m ...
Ajax's user avatar
  • 155
1 vote
2 answers
92 views

Given an array of size $n$, return a sorted array of floor($n^k$) elements for some $k<1$

We are given an array of size $n$ (it is not specified if we have an integer array, a specific range or any other assumptions), which might be unsorted, and a real number as a constant $k<1$. We ...
LearningSomeone's user avatar
0 votes
1 answer
63 views

Comparisons using Quicksort with the median as the pivot

Background Using a simplified Quicksort algorithm where the first element of the array is assigned as the pivot we get the following pseudocode for the algorithm: Quicksort($a$): (1) If length($a$) $...
FD_bfa's user avatar
  • 103
0 votes
0 answers
16 views

Need help verifying the complexity of an algorithm [duplicate]

I have the following algorithm which takes as an input a non negative integer n : i = n while i > 0 do : $\,$ $\,$ $\,$ $\,$i = i - 1 $\,$ $\,$ $\,$ $\,$j = 1 $\,$ $\,$ $\,$ $\,$ $\,$ $\,$ $\,...
pierrovoltela's user avatar
0 votes
0 answers
38 views

Researching the complexity of a dynamic array with insert-last(x) and delete-last() operations

In this question I need your help researching time complexity of a dynamic array with insert-last(x) and delete-last() operations: We define a data structure and call it dynamic array, we define the ...
T-Caster's user avatar
0 votes
1 answer
33 views

if f(n),g(n) =! 0 , for every n > 0 , and f(n) = Ω(g(n)) , then does this mean that 1/f(n) = O(1/g(n))

Basically what i am trying to prove is this : $f(n),g(n) \neq 0\quad , n>0 \ \ \ \ and f(n)=Ω(g(n)) \ \ \ , \ then \frac{1}{f(n)}=O(\frac{1}{g(n)}) $ I guess that if we take the definition of $f(...
pierrovoltela's user avatar
1 vote
1 answer
56 views

The value of $r$, with $r≤ b$, that minimizes the expression $(b/r)(n+2^r)$ in the analysis of the radix-sort algorithm

In chapter 8 of the book "Introduction to Algorithms" by Cormen, Leiserson, Rivest, and Stein, lemma 8.4 is proved. (my question is after the proof of the lemma) Given $n$ $b$-bit numbers ...
emacos's user avatar
  • 121
3 votes
2 answers
148 views

An algorithm that is $O(n^{\log(n)})$

After having searched for a while, and after having read this https://stackoverflow.com/questions/1592649/examples-of-algorithms-which-has-o1-on-log-n-and-olog-n-complexities I was just wondering: is ...
Numb3rs's user avatar
  • 131
1 vote
2 answers
46 views

If we have f(n) ∈ O(h(n)) and g(n) ∈ Ω(h(n)), does that mean that f(n) + g(n) ∈ Θ(h(n))?

It is quite easy to prove that f(n) + g(n) ∈ Ω(h(n)), but I am having trouble with proving/disproving that f(n) + g(n) ∈ O(h(n)). Someone suggested that this question answers mine, which it doesn't. ...
figsinwinter's user avatar
0 votes
5 answers
223 views

Is $n^n$ is a big-oh n factorial

Is it true or false that $n^{n} \in \mathcal{O}(n!)$ ? Any suggestions how to prove/disprove this statement?
taycants's user avatar
0 votes
5 answers
149 views

Find the asymptotic bound for the recurrence relation: $T(n) = T(\sqrt{n}) + 5n$

I've tried to expand the recursion: $$T(n) = T(n^{\frac{1}{2}}) + 5n = T(n^{\frac{1}{4}}) + 5(n^{\frac{1}{2}} + n) = T(n^{\frac{1}{8}}) + 5(n^{\frac{1}{4}} + n^{\frac{1}{2}} + n)$$ We have a total of $...
Yoxbox's user avatar
  • 3
0 votes
2 answers
54 views

Can a program that terminates have a running time of infinity? (Or not have an upper bound)

Can we have an algorithm that takes some input and does something random to it (in such a way that the algorithm does terminate) which does not have a worst-case running time upper-bound? A (non-)...
proof-of-correctness's user avatar
0 votes
2 answers
64 views

Comparison between big-Ω and ω notations

Example of function f(x) such that it is true that f(x) = Ω(g(x)) but that it is not true that f(x) = ω(g(x))
emacos's user avatar
  • 121
0 votes
3 answers
111 views

How do I solve this recurrence equation?

I have to express the solution of the recurrence equation T(n) = T(an) + n where a is a constant, 0 < a < 1, in terms of θ using the iteration method. I am unsure of how I calculate the cost of ...
afahey03's user avatar
1 vote
1 answer
40 views

What's the most scalable solver of this problem?

Consider the following optimisation problem that its size is parameterised by $n$ (width) and $m$ (depth): Find $w_1, w_2, \ldots, w_n$ that minmises: $$ \min \Big[w_1x_1^0 + w_2x_2^0 + \ldots + ...
caveman's user avatar
  • 115
2 votes
2 answers
88 views

Prove that $O(\sum_{i=0}^{h}{2^i\times(h-i)}) \sim O(2^h)$

I want to prove that, $$\sum_{i=0}^{h}{2^i\times(h-i)} \sim O(2^h).$$ I did come up with the below proof, $$\sum_{i=0}^{h}{2^i\times(h-i)} \sim O(\sum_{i=0}^{h-1}2^{h-1}) \sim O(h2^h),$$ but as it is ...
Ashkan Khademian's user avatar
0 votes
0 answers
16 views

least collection of node disjoint paths that cover a given set of vertices

Given a directed graph G (with cycles) with source and target, and a set of interested vertices S. we want to find a small n collections of vertice-disjoint-paths (path only have common nodes in ...
Yufei Zheng's user avatar
0 votes
1 answer
39 views

Shell's Increments Worst Case Analysis

My textbook claims the worst-case running time of Shellsort with Shell's increments is $Ω(N^2)$, but this analysis is done when $N = 2^m$ for a positive integer $m$. I see why the proof would work for ...
GuestUser's user avatar
-3 votes
1 answer
37 views

How do I prove the following relationship between big-theta notation and logarithms?

Prove that: $\lg (\Theta(n))=\Theta(\lg n)$
Arham Mehta's user avatar
-3 votes
2 answers
85 views

How to find the standard theta notation of this?

Hi i am practising standard theta notation: How could i find the standard theta notation of the following : 2n + 3n^2(log n)^3 + 2 and ...
zeek's user avatar
  • 1
2 votes
1 answer
52 views

Finding general time complexity for recurrence relation $T(n)=aT(n/\alpha)+bT(\beta n/\alpha)+f(n)$

I was given an assignment in which I had multiple recurrence relations and I had to find their Big-oh time complexities. Nearly all of the recurrence relations were of the form as under: $$T(n)=aT(n/\...
Paras Khosla's user avatar
-1 votes
2 answers
85 views

How to prove this because if we consider big-oh than logn^2 <= log n + 5 can never happen if n grows?

f(n) = log n^2; g(n) = log n + 5 => f(n) = Θ (g(n)) I think we can prove this for omega but how can we prove it for Big oh ? because if we simplify it to logn + logn <= logn +5 => logn<=...
user157232's user avatar
0 votes
0 answers
45 views

Basic Clique Complexity Question

A question in a textbook says, suppose the regular Clique problem, which takes as input a graph G and a natural number k, and returns whether or not G has a clique of size >= k, can be decided in ...
Abhishek Manikandan's user avatar
0 votes
4 answers
256 views

What is the lower bound of n factorial

The upper bound of $n!$ is $O(n^n)$. But I am not getting a way to compute the lower bound of n!. We can write $n! = n\times(n-1)\times(n-2)\times\dots\times 1$. I can easily put all the terms as 1. ...
user529767's user avatar
0 votes
0 answers
20 views

Order of time complexity in computing $R\sin(2\alpha)$ VS $2R\sin(\alpha)\cos(\alpha)$

I was wondering, in terms of complexity and "precision", what are the differences, if any, netween the computation of $$2R \sin(\alpha)\cos(\alpha) \qquad \qquad \text{and} \qquad \qquad R\...
Henry's user avatar
  • 101
0 votes
0 answers
57 views

asymptotic approximation ratio vs absolute approximation ratio?

I am trying to learn about approximation algorithms. In some research papers, it is mentioned about the absolute approximation ratio. what does the absolute approximation ratio mean? is it different ...
ryan chandra's user avatar
-4 votes
1 answer
52 views

How to solve this recurrence relation: T(n) = R(n-1) + n log n R(n) = T(n-1) + n^2

How to solve this recurrence relation: T(n) = R(n-1) + n log n R(n) = T(n-1) + n^2
Aziz's user avatar
  • 1

1
2 3 4 5
29