# Questions tagged [asymptotics]

Questions about asymptotic notations and analysis

1,457 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
1 vote
25 views

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 ...
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 ...
1 vote
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,...
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 ...
• 173
1 vote
88 views

• 113
1 vote
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. ...
• 15
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 ...
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 ...
• 15
77 views

• 109
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 ...
• 569
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) =...
• 121
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-...