Questions tagged [asymptotics]
Questions about asymptotic notations and analysis
1,460
questions
1
vote
1
answer
796
views
How can I prove that '+' is same as max?
I know that, $\max(m, n) = O(m+n)$.
But my teacher uses, $$m+n=\Theta(\max\{m, n\}).$$
Anyone explain me why the above expression is true.
- 510
1
vote
1
answer
40
views
Proving $f(n) = 1 + c + c^2 + \cdots + c^n = \Theta(1) $
How can I prove that the function $$ f(n) = 1 + c + c^2 + \cdots + c^n $$ is $\Theta(1)$ when $c<1$?
where $n \in \mathbb{N}$ and $c \in \mathbb{R}$, with $c>0$. Can I use limits?
Thank you in ...
- 11
1
vote
2
answers
2k
views
Arrays. Find row with most 1's, in O(n)
Suppose that each row of an $n \times n$ array $A$ consists of 1's and 0's such that, in any row of $A$, all the 1's comes before any 0's in that row. Assume $A$ is already in memory, describe a ...
- 29
1
vote
2
answers
53
views
What does "computer steps" mean in this runtime definition?
My algorithms textbook defines $T(n)$ as "the number of computer steps needed to compute fib1(n)" (where fib1(n) ...
- 111
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 ...
- 29
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
...
- 29
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 $...
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 ...
4
votes
2
answers
101
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) {
...
- 43
0
votes
0
answers
13
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
...
- 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 ...
- 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)
- 1
2
votes
2
answers
184
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 ...
- 23
4
votes
2
answers
147
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 ...
- 43
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^{...
