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.
370
questions
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 ...
CommunityBot
- 1
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^{...
CommunityBot
- 1
2
votes
3
answers
147
views
How to simplify $O(\log (n!))$?
I have a problem with this time complexity: $\log (n!)+\frac{5}{2}n\log\log n$. I'm not sure how to deal with the $n!$ term. I know from calculus class that the sequence $n!$ is bigger than any ...
- 131
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(...
CommunityBot
- 1
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[...
D.W.♦
- 164k
-1
votes
3
answers
126
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:
...
- 331
0
votes
1
answer
27
views
Recurrence relation simplification
I have initial condition $𝑛_1=2, 𝑣_1=1$, and the given recurrence relations: $𝑛_{𝑖+1}=2𝑛_𝑖,$ $𝑣_{𝑖+1}=2𝑣_𝑖+\frac{1}{2} 𝑛_𝑖$
I need to show that that,
$v_i=\Theta(n_i\log n_i).$
I observe ...
- 1,934
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 ...
CommunityBot
- 1
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 :
...
CommunityBot
- 1
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 ...
CommunityBot
- 1
0
votes
1
answer
49
views
Relationship between $\omega$ and o
I have for every constant $c$ (no matter how large) and for every $\epsilon >0$(no matter how small), how can I show that
$$n.e^{\sqrt{\log n}}=\omega(n\log^c n)\\
n.e^{\sqrt{\log n}}=o(n^{1+\...
- 136
1
vote
1
answer
45
views
Is $n\log n + n\log \log n = \Theta(\log n)$?
To show $n\log n + n \log(\log n) = \Theta(\log n)$. Is this even correct? It can be easily shown that, $n \log n + n \log(\log n)$ is $O(n\log n)$ and also $\Omega(n\log n)$, with constants $2$ and $...
- 1,294
10
votes
2
answers
3k
views
Are there any functions with Big O (Busy Beaver(n))?
So, I was reading this article by Scott Aaronson on big numbers, and he mentioned that the Busy Beaver sequence increases faster than all sequences computable by Turing Machines. Faster than ...
- 312
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}
\...
CommunityBot
- 1
12
votes
5
answers
6k
views
Does it make sense to say Big Theta of 1? Or should we just use Big O?
Does saying $f(x) = \Theta(1)$ provide any extra information over saying $f(x) = O(1)$?
Intuitively, nothing grows more slowly than a constant, so there should be no extra information in specifying ...
- 7,158
1
vote
1
answer
809
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.
- 1,294
0
votes
1
answer
80
views
Arora and Barak: Exercise 0.2. (b)
I am reading Arora and Barak's book "Computational Complexity: A Modern Approach". I am doing exercise 0.2. (b): For each of the following recursively defined functions $f$, find a closed (...
- 243
2
votes
3
answers
100
views
$f(n)=n^{100}$, $g(n)=2^{n/100}$, determine whether $f=O(g)$
I am reading Arora and Barak's book "Computational Complexity: A Modern Approach". I am doing EXERCISE 0.1.(b): $f(n) = n^{100}$, $g(n)=2^{n/100}$, determine whether $f=O(g)$.
Here's what I ...
- 31.5k
-1
votes
3
answers
53
views
O-notation confusion
I'm reading CLRS and I can't understand this part:
in n-100<=c
why we can't choose 101 for n (and more) and any value of c that's >=1?
- 33
1
vote
1
answer
42
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 ...
- 1,294
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
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 ...
CommunityBot
- 1
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?
CommunityBot
- 1
1
vote
3
answers
201
views
When do we multiply or add the time complexities of loops?
I am confused about calculating the time complexity of the following function.
...
- 31.5k
1
vote
1
answer
30
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 $...
- 1,934
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 ...
CommunityBot
- 1
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
51
views
Big O notation of T(n) = T(n/2) + O(log n) using master theorem?
I am aware that the algorithm has 1 recursive call of size n/2 and the non-recursive part takes O(log n) time.
Master theorem formula is T(n) = aT(n/b) + O(n^d). In this case a = 1, b = 2, but I am ...
- 31.5k
4
votes
2
answers
106
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) {
...
- 1,378
0
votes
1
answer
136
views
1
vote
2
answers
54
views
Understanding Time Complexity Calculation for Factorial and Exponential Algorithms
I'm trying to wrap my head around how to calculate the time complexity of algorithms that exhibit factorial (𝑛!) or exponential (2^𝑛) growth rates.
Specifically, I want to understand the thought ...
0
votes
2
answers
211
views
How to prove Big-O when $f(n)$ is defined sectionwise
I'm given a function which is defined based on a condition, for example
$$
f(n)
= \begin{cases}
4n+1, \ \text{n is even}\\
3n^2+2, \ \text{n is odd}
\end{cases}.
$$
I have to prove or ...
- 127
2
votes
2
answers
265
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
1
vote
1
answer
776
views
why quicksort can have a best big o notation of (n log n)
Why does quicksort have a big $O$ notation of $(n \log n)$.
I would like some help understanding what exactly $(n \log n)$ is, and then how it applies to quicksort.
Also in $(n \log n)$, what is the ...
- 105
7
votes
1
answer
599
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 ...
- 1,097
2
votes
2
answers
185
views
4
votes
2
answers
541
views
How does knowing the input size make the time complexity of a function constant?
After reading the question and answers on Time complexity of min() and max()? I would like to clear up some confusion on the relation between time complexity and size of input.
First, I've noticed ...
- 560
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
2
votes
2
answers
220
views
Is $(n^5 + n^7)\in \Omega(n^7)$? Shouldn't it be in $\Omega(n^5)$?
Is $(n^5 + n^7)\in \Omega(n^7)$? Shouldn't it be in $\Omega(n^5)$?
I understand Omega to be a "lower bound" on a function. Shouldn't the largest lower bound on the function $n^5 + n^7$ be $n^5$? (...
- 1,934
2
votes
2
answers
87
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 ...
- 31.5k
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
1
vote
1
answer
38
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.
...
- 31.5k
-1
votes
2
answers
79
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}...
- 1,294
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 ...
- 29.6k
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 ...
- 1,294
1
vote
1
answer
269
views
Time complexity of algorithm with three loops and if statement
Suppose I have this c++ code:
...
- 1,294
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
680
views
Θ, O and Ω, and how they relate to each other as subsets
I am trying to understand how $\Theta(n)$, $O(n)$, and $\Omega(n)$ relate to each other as sets and want to make sure I'm on the right track.
I get that $Θ(n) \subseteq O(n)$ since $Θ(n)$ is stronger ...
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 ...
- 6,237
0
votes
1
answer
77
views
Why, for $f(n) = n \cdot \sqrt n$ and $g(n)=n^2/\log n$, we have $f(n) = o(g(n))$?
Let $f(n) = n \cdot \sqrt n$ and $g(n)= \frac{n^2}{\log n}$. Why is $f(n) = o(g(n))$?
Could you please explain to me why this is so? I have tried l'Hôpital's rule but it doesn't add any ...
- 16.8k