Skip to main content

Questions tagged [asymptotics]

Questions about asymptotic notations and analysis

Filter by
Sorted by
Tagged with
0 votes
1 answer
30 views

Formula regarding Big-Oh (and a bit math)

I want to show that $O(max\{f(n),g(n)\}) = O(f(n)+g(n))$, and wonder if this argument works out! Let $f(n) = max\{f(n),g(n)\}$. If otherwise we could just switch cases. $f(n) \leq ch(n)$ for some ...
Science Guy's user avatar
0 votes
2 answers
52 views

Showing that a pseudocode algorithm runs in $\Omega(n^3)$

I want to show that this pseudocode algorithm runs in $\Omega(n^3)$. Input: An n-element array A of numbers, indexed from 1 to n. Output: The maximum subarray sum of array A ...
Science Guy's user avatar
1 vote
1 answer
25 views

Emphasizing the Coefficients of the Leading Order and Using Big O Notation for the Remainder

I am trying to understand the correct application of Big O notation to polynomial expressions, including terms with negative coefficients. For example, consider the polynomial $2n^3-2n^2+n+1$, where $...
Byeongyong Park's user avatar
0 votes
0 answers
15 views

Asymptotic bound

How can this relation : $$ T(n)=4^n + 12 \cdot \sum^{n-2}_{i=1}{T(i)} $$ $$ T(1) = 1 $$ be evaluated to asysmtotic bound (Big O notation)? It could be easy if the upper bound of the sum were ...
User1342221's user avatar
4 votes
2 answers
96 views

How to Determining the Big O Complexity of a Recursive Function?

I'm struggling to determine the correct time complexity of a recursive function from an exam question. The function definition is as follows: fun (n) { ...
deaa aldeen's user avatar
0 votes
0 answers
12 views

Relation between running time of Insertion sort and number of inversions

What is the relationship between the running time of insertion sort and the number of inversions in the input array? Justify your answer. Consider Insertion sort ...
Omkar's user avatar
  • 1
-1 votes
1 answer
54 views

Proving tight bound Θ for worst-case running time of an algorithm without proving lower bound Ω

See this answer first: Proving worst-case running time is in $\Omega(n^2)$ Understanding the linked answer for insertion sort leads to the following statement. Prove that the statement is either ...
jam's user avatar
  • 13
-2 votes
1 answer
40 views

Proving a statement involving asymptotic notation

I need help with this question. If it’s possible to do this without limits, please show. Thanks. Q: If f(n) is Ω(n) and g(n) is O(n), then prove or disprove the following statement: f(n) is O(n)
anaya's user avatar
  • 1
2 votes
2 answers
145 views

Time Complexity O-Notation for Kociemba, Korf, and Thistlethwaite's Algorithms? (Rubik cube)

I'm currently studying the 3x3x3 rubik-cube-solving algorithms developed by Kociemba, Korf, and Thistlethwaite and I'm interested in understanding their computational complexities. Could someone ...
Lisa's user avatar
  • 23
4 votes
2 answers
145 views

What does $o_n(1)$ mean?

I'm trying to read the following article, and in the abstract they write: Let $\xi$ be a non-constant real-valued random variable with finite support, and let $M_n(\xi)$ denote a $n\times n$ random ...
L. breitman's user avatar
0 votes
1 answer
29 views

Solving recurance relation with master theorem

I'm studying asympotic analysis and I encountered this problem: Given a recurrence relation: $$T(n)= aT(n/b)+cn^a (n>0;a>=1;b>=1)$$ prove that if $a>a^b$ then T(n)=$\mathfrak\theta(n^{...
hải nguyên đỗ's user avatar
0 votes
1 answer
25 views

Is $O(n^{f(n)})$ superexponential if $f(n)$ is a polynomial function such that $f(n) > n$ as $n$ approaches $\infty$?

I know that exponential time complexity is $ O(k^n) $, where $k$ is some constant and $n$ is the input size, and that subexponential time is anything slower than that, $o(k^n)$ . If we define ...
Karlo Vizec's user avatar
2 votes
1 answer
76 views

How to solve the recurrence $ T(n) = 4T\left(\frac{n}{2}\right) + \frac{n}{\lg n} $ in terms of $\Theta$?

I'm attempting to solve the recurrence relation: $$ T(n) = 4T\left(\frac{n}{2}\right) + \frac{n}{\lg n} $$ in terms of its asymptotic behavior ($\Theta$), specifically using the first case of the ...
Ferran Gonzalez's user avatar
1 vote
2 answers
58 views

How to Solve the Recurrence Relation $T(n) = 8T\left(\frac{n - \sqrt{n}}{4}\right) + n^2$ in terms of $\Theta$?

The provided recurrence relation is as follows: $$ T(n) = 8T\left(\frac{n - \sqrt{n}}{4}\right) + n^2 $$ The goal is to express the solution in terms of the asymptotic notation $\Theta$. Unfortunately,...
Ferran Gonzalez's user avatar
7 votes
1 answer
587 views

Possible Mistake in Skiena's Algorithm Design Manual

In Skiena's book Algorithm Design Manual, 3rd Edition, it is claimed on page 45 that $$ mn - m^2 + m \in \Omega(mn) $$ where $m,n \geq 0$ and $m \leq n$. I claim that this is in fact false, with the ...
Joshua's user avatar
  • 173
1 vote
0 answers
88 views

What is the difference between $O$ and $\widetilde{O}$?

We know that $\widetilde{O}(f(n))$ — $O$ with a tilde above it — which means $O(f(n) \text {polylog}(f(n)))$, i.e., $O(f(n) (\log f(n))^k)$ for some $k$. Also I have seen in Wikipedia that $n2^n=\...
A. H.'s user avatar
  • 498
1 vote
1 answer
556 views

Big-O time complexity for this code snippet

...
Angel's user avatar
  • 11
2 votes
2 answers
69 views

Big O notation of $O(n/(m-n))$

I'm new to the complexity theory and have a basic question about the big-O notation that I encountered. I came across a complexity of $O\big(\frac{n}{m-n}\big)$, where both $n$ and $m$ are independent ...
user185671631's user avatar
1 vote
2 answers
86 views

Bound $T$ asymptotically tight | Recursive trees

Let $\alpha \in (0, 1),\space l \geq 2$ and $T: \mathbb{N}\rightarrow\mathbb{R}^+$ such that, $T(n) = \begin{cases} n^l + T(\alpha n) + T((1-\alpha)n) & : n > 1 \\1 : n=1 \end{cases}$ Bound $...
X4J's user avatar
  • 113
1 vote
1 answer
35 views

Big O, Understanding when the increment is doubling

I am trying to find the Big O notation of this code below, really its the big theta, but whatever I believe its the same in this case. ...
Kuro's user avatar
  • 15
0 votes
1 answer
38 views

What is the "big theta" order of the solution of T_n = T_(n/2) + log n, n > 0?

What method(s) could be used to solve this? I am still new to this stuff and would appreciate detailed justification for every step as well as some intuition and the examination of all possible viable ...
user79644's user avatar
0 votes
1 answer
57 views

Big O Notation, Why do we ignore everything inside the log?

Okay, so I understand implicitly why we might write f(n) = log 3n = O(log n) but I don't really understand why lets say ...
Kuro's user avatar
  • 15
-1 votes
2 answers
77 views

Adding O(x)+O(x-1)+O(x-2)+

I have a function $f$ such that is the sum of big O terms, such as $$f=\left[\sum_{i=1}^x \frac{1}{i}\right] +O\left(\frac{\ln^4 x}{x}\right)+O\left(\frac{\ln^4 x-1}{x-1}\right)+O\left(\frac{\ln^4 x-2}...
fox's user avatar
  • 183
1 vote
1 answer
108 views

Is there a [non-comparative] sorting algorithm, sorting an array in $o(n \log n)$?

We have shown that any comparative sorting algorithm has the worst-case complexity of $\Omega(\log (n!)) = \Omega(n \log n)$, as it has to cover all the ways a permutation can be, and according to the ...
sbh's user avatar
  • 51
1 vote
2 answers
53 views

Solving recurrence by iteration, choosing base case

A question I am to answer wants me to find the big O of a recurrence, I am doing it with the iteration method. For the base case, which we get after applying the recurrence $i$ times, can we make this ...
user438409385's user avatar
0 votes
1 answer
38 views

Conflicting definitions surrounding asymptotic notations. Please advise!

I spent the last couple of days trying to understand the different asymptotic notations but it seems I'm hitting some conflicting information. For context, I believe I've understood the formal ...
ten_to_tenth's user avatar
-1 votes
2 answers
266 views

Is the time complexity of a loop that simultaneously increments and multiplies $O(\log_k n)$ when $k = 1$?

Is the time complexity of for(int i=0;i<n;i++){i*=k;} $O(\log_k n)$? The problem is number 8 from GeeksForGeeks: https://www.geeksforgeeks.org/practice-...
HereToTryHelp's user avatar
2 votes
1 answer
33 views

Expected number of mistakes grows logarithmically in number of iterations - improving performance?

I am reading a paper (link) in which an algorithm proposes a solution $\hat{\mathbf x}^{(t)}$ in each iteration $t = 1, \dots, T$, and each time, learns the true solution $\mathbf x^{(t)}$, so we ...
caitlin's user avatar
  • 21
2 votes
1 answer
393 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
115 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
73 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
40 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
38 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
64 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
26 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
49 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
23 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
38 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
52 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
82 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
50 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
102 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 ...
big-Oaf's user avatar
  • 117
-1 votes
3 answers
67 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
74 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 ...
Zee's user avatar
  • 243
0 votes
2 answers
95 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
  • 109
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
  • 569
-1 votes
1 answer
47 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
266 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
1 vote
0 answers
44 views

Shell sort algorithm analysis

Given this Shell sorting algorithm implementation: ...
Kim's user avatar
  • 21

1
2 3 4 5
30