Questions tagged [big-o-notation]
Big O Notation is an informal name of the "O(x)" notation used to describe asymptotic behaviour of functions. It is a special case of Landau notation, where the O is the Greek letter capital omicron. Please consider using the [landau-notation] tag instead if your question is related to small omicron, omega, or theta in Landau notation.
55
questions with no upvoted or accepted answers
3
votes
0
answers
86
views
What's the fastest known non-galactic algorithm for matrix multiplication of large matrices
"A galactic algorithm is one that outperforms any other algorithm for problems that are sufficiently large, but where "sufficiently large" is so big that the algorithm is never used in ...
- 356
3
votes
0
answers
106
views
Induction pitfalls with O notation and recursion
I read the following in CLRS 3rd Ed:
I'm not sure I understand exactly how to avoid this pitfall.
How would one know that the $\mathcal{O}$ notation in this case grows with $n$ and is thus not ...
1
vote
0
answers
91
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=\...
- 593
1
vote
0
answers
37
views
Auxiliary Space Complexity of Dictionaries whose Keys are Iterables of Variable Size
Recently, I began delving into complexity analysis with dictionaries. More specifically, I have been looking at auxiliary space complexity. For the most part, this type of analysis has been ...
- 111
1
vote
3
answers
102
views
Upper bounding this expression
I need to prove that the following expression is $\mathcal O(n \log n)$ with the substitution method: $$ T(n) \leq 3\log n + n + \frac{6}{n}\sum^{n - \frac{\log n}{3}}_{i=\frac{\log n}{3}} T(i)$$
This ...
- 73
1
vote
0
answers
51
views
Runtime of this algorithm
I have an algorithm with running time that satisfies
$$ T(n) \leq n + \frac{1}{n}\sum^{n-1}_{i=0}(T(i) + T(n-i)),$$ and $T(0) = 0$. I was able to show that $T(n) = \mathcal O(n\log n)$ with a leading ...
- 257
1
vote
0
answers
67
views
Algorithms with different upper and lower bounds
I am preparing a list of algorithms for which big theta expression for (worst case) runtime is not known. This is for a class to demonstrate the point that tight analysis of an algorithm may not be ...
- 11
1
vote
0
answers
46
views
Does creating an array count as a primitive operation under the RAM model?
int[] arr = new int[10];
Would this count as a single primitive operation under the RAM model or would it be 10 operations as we are allocating 10 memory locations ...
- 11
1
vote
0
answers
40
views
Does clog(n)-c+1 work for T(n)=T(⌈n/2⌉)+1=O(log(n)) after induction?
The given problem is from CLRS, exercise 4.3-2.
Show that the solution of T(n)=T(⌈n/2⌉)+1=O(log(n))
I decided to prove T(n) ≤ clog(n) and this is the result I got:...
- 11
1
vote
0
answers
119
views
Space usage of recursive functions with no return
Consider an algorithm for reversing a sequence given below:
...
- 135
1
vote
0
answers
51
views
Complexity Values for Specific Code/Functions
(1) Assume a function $f:\mathbb{Z^+}\rightarrow\mathbb{R}$ that's defined in a way that utilizes, say, eight basic computations, including addition, subtraction, division, multiplication, (positive ...
- 11
1
vote
0
answers
854
views
What is Big O of a loop with square root inside?
Knowing that O(n^2) > O(nlogn) > O(n) > O(sqrt(n)) > O(logn) > O(1) and having below python code:
...
- 111
1
vote
0
answers
46
views
Big O notations of some functions
What is the big-O notation of the following functions :
$\displaystyle\sum_{i=1}^n \left(\begin{array}{c}
n-1\\
i
\end{array}\right)\\\\
\displaystyle\sum_{i=1}^{n} \sum_{j=1}^{n-i}(3j)\\\\
n^{\...
- 163
1
vote
0
answers
42
views
Prove that for all functions g: N -> R>=0, and all numbers a in R>=0, if g in Omega(1) then a + g in Theta(g)
Here is a more readable version of the question:
Prove that for all functions $g: \mathbb{N}\to\mathbb{R}^{\geq 0}$, and all numbers $a \in \mathbb{R}^{\geq 0}$, if $g \in \Omega(1)$ then $a + g \in \...
user116370
0
votes
0
answers
52
views
Graph Problem Time Complexity
I'm trying to devise an algorithm for the following prompt from LeetCode's daily challenge:
You are given an undirected weighted graph of n nodes (0-indexed), represented by an edge list where edges[...
0
votes
0
answers
19
views
Do I need to display constants in the step count method
I tried looking this up before coming here but I couldn't find any resources. If there is a post that already exists that can explain this please let me know so I can close this one.
I am creating ...
- 111
0
votes
0
answers
17
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 ...
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^{...
0
votes
0
answers
42
views
Calculating Runtime Complexity: Recursion + Memoization vs Dynamic Programming (with example)
For cases where recursion is used as well as memoization (so that a number of subtrees of what would otherwise be the overall recursive call tree are each replaced to be ...
- 101
0
votes
1
answer
105
views
Find a substring length $k$ with maximum occurrences
Given a string length $S$, find a substring length $k$ that has the most occurrences in the given string.
We want $O(S)$ time complexity in an average case.
I think the solution lies in sophisticated ...
- 183
0
votes
1
answer
114
views
Struggling with Recurrence Relation using Telescoping Approach
I have the following recurrence relation that I am trying to solve using the telescoping approach:
$T(n) =
\begin{cases}
T(\frac{n}{4})+ n^2 & \text{for } n \geq 4
\\
1 & \text{otherwise}
\...
0
votes
0
answers
86
views
Ranking functions by order of growth
Did I correctly rank these functions by order of growth? I ranked them from smallest to largest (left to right). I have to eventually prove this ranking, so just looking to make sure that I have the ...
0
votes
1
answer
63
views
Binary search calculating complexity big o
I'm studying recursion and a i have a doubt about the running time complexity of the binary search. I didnt understand this passage in my book :
...
- 3
0
votes
1
answer
56
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(...
0
votes
1
answer
57
views
Trying to understand the time complexity of IDDFS
I'm trying to break down the Time complexity algorithm for IDDFS. Acknowledging that in general my understanding of maths is not that great. So I will be trying to talk things out.
For BFS it is ...
- 1
0
votes
0
answers
48
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 ...
0
votes
2
answers
75
views
Derive complexity from recurrence relation
On the Wikipedia article on Karatsuba algorithm (https://en.wikipedia.org/wiki/Karatsuba_algorithm#Time_complexity_analysis) it is stated:
$T(n) = 3 T(\frac{n}{2}) + cn + d$
And then, by invocation of ...
- 241
0
votes
0
answers
49
views
Can 0 be a tight upper bound of -4n?
I'm newbie in algorithm time complexity.
I had a function, f(n) = 2n2 - 4n.
I have to proof that f(n) = O(n2).
We can take it ...
0
votes
2
answers
92
views
What is the asymptotic runtime of the below equation?
What is the asymptotic of
${n \choose 3} \log ^4n$ ?
I know that ${n \choose 3}$ is in $\cal O (n^3)$, but what about the term $log^4n$ and what about the product of the two?
- 135
0
votes
0
answers
442
views
Is reduction from Rudrata/Hamiltonian path to Rudrata/Hamiltonian cycle O(1)?
I am reading about P and NP and looking at the reduction of a Rudrata/Hamiltonian path to a Rudrata cycle. I think adding an extra node and 2 edges connecting the start, ...
- 659
0
votes
0
answers
85
views
Prove or disprove $T(n) = T(\lfloor\frac{n}{2}\rfloor+1)+1=O(\log(n))$
Lets define function $T(n)$ as
\begin{align*}
T(1) &= T(2) = 1\\
T(n) &= T(\lfloor\frac{n}{2}\rfloor+1)+1 \text{, where }n\ge 3.\\
\end{align*}
Does $T(n)=O(\log(n))$? I have no idea how to ...
0
votes
3
answers
108
views
Help with model answer for time complexity
Hi I cannot understand why the best case for line 3 is n-1 and why it isnt just always n?
I tried to write this in python to ...
- 81
0
votes
0
answers
80
views
Prove that $T(n)=\omega(n)$?
Edit: can someone provide clear answer with all details
Given:
$T(n)=T(n/10)+T(an)+n$ while $a$ is a const and $T(n)=1:(n<10)$
I was asked to find the minimum value for $a$ for which $T(n)=\omega(n)...
0
votes
0
answers
36
views
The following time complexity is right for the given algorirthm
Calculate the complexity of the algorithm as follows O (n ^ 2) Would it be correct?
...
0
votes
0
answers
2k
views
Time complexity for computing the highest degree vertex
Consider an undirected and unweighted graph with $n=|V|$ nodes and $m=|E|$ edges stored in adjacency matrix format.
What is the time complexity of finding the highest-degree vertex, assuming the ...
- 101
0
votes
0
answers
52
views
Time complexity about Maximum subarray
I recently came across a function called the strawman algorithm which the pseudo code looks like this:
...
- 101
0
votes
0
answers
52
views
Big $O$ approximation for $T(n)=T(n-i)+T(n-(\frac{n}{m}-i))$
I have the following complexity equation: $T(n)=T(n-i)+T(n-(\frac{n}{m}-i))$ with the base case $T(m)=1$.
Is it possible to calculate a big $O$ approximation for such equation? What is the right ...
- 49
0
votes
0
answers
35
views
Big O notation of $\left(\begin{array}{c} n\\ \frac{n}{2} \end{array} \right)$
What is the O-notation (or $\Theta$ notation ) of $\left(\begin{array}{c} n\\ \frac{n}{2} \end{array} \right)$ ?
Can I use Sterling approximation : $n! = \Theta(\sqrt{n}\left(\frac{n}{e}\right)^n)$ ...
- 163
0
votes
0
answers
19
views
Question in regards to how an O(N^3) looks like using while/for loops
would the code below be considered O(N^3)?
while (...) {
while (...) {
}
while (...) {
}
}
- 1
0
votes
0
answers
1k
views
What is the Big theta of $(\log n)^2+2n+4n+\log n + 50$?
$f(n)=(\log n)^2+2n+4n+\log n + 50$
I am trying to mathematically prove that $f(n)$ falls under some time complexity big theta. My guess is that it is $(\log n)^2$ because it is the dominant term.
I ...
- 101
0
votes
0
answers
67
views
Summing big-O-notation
prove or disprove
$$\text{If } f(n)=g(n)+h(n), \text{ then } O(f(n)) = O(g(n))+O(h(n)).$$
I have no idea about where to begin.
what are the theories which should be used here?
- 111
0
votes
0
answers
140
views
How to find running time complexity of divide and conquer method without Master Theorem
I understand that Master Theorem can be used to solve divide-and-conquer run times if they're in the form of $T(n) = aT(\frac{n}{b}) + n^clog^k(n)$ The reason behind it has to do with drawing a tree ...
user109386
0
votes
0
answers
37
views
Asymptotics and logarithms/exponents
We have four categories:
additive constants, multiplicative constants, polynomials, and
exponentials
When determining the growth order of functions, we only care about polynomials and ...
- 1
0
votes
2
answers
128
views
How to show working for summing of Big O notation
The equation below is intuitively correct, but how do you show that this is actually the case? What is the working out needed?
$$\sum_{i=1}^{n-1}O(\lg n)=O(n\lg n)$$
- 123
-1
votes
3
answers
125
views
Time complexity of algorithm involving function calls
Me again.
This time I have a more general question.
Suppose I have the following code snippet:
...
- 175
-1
votes
2
answers
158
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<=...
-1
votes
2
answers
364
views
what is the time complexity of this while loop nested in a for loop?
I'm really having rough time understanding the time complexities of nested loops. So, please help me out in this code. The code is on sliding window with changing length:
...
- 1
-1
votes
1
answer
88
views
How to resolve the clash between definition of Big O notation and Inductive Hypothesis when proving running time by substitution method?
Suppose you have to prove the solution to the following recurrence by Induction,
$$
T(n)=
\begin{cases}
\Theta(1), & n=1 \\
2 T(\lfloor n/2 \rfloor)+\Theta(n), & n>1
\end{cases}
$$
Here, $\...
- 179
-1
votes
1
answer
60
views
Complexity of T(n)=2T(n-1)
I built a recursion tree like this:
0
/ \
0 0
/\ /\
... ...
So the tree has height n, and width $2^n$.
But if the sum of all levels is $\sum_{i=0}^{n}...
- 1
-1
votes
1
answer
661
views
Find the values for n0 and the constant factor c such that f(n) = n log n is Ω(n)
I was recently introduced to big O and big Omega, as well as big theta. I know that big O is the worse case scenario in terms of runtime, big Omega is the best case scenario, and big theta is in ...
