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.
380 questions
1
vote
1
answer
52
views
Parameter selection and Big-O notation
This may seem like a pedantic or trivial question but it's something that's been irking me since working through some problems in a competitive programming manual.
One of the problems dealt with ...
- 11
1
vote
1
answer
96
views
Big O and Omega, how can they be different for a specific case(worst/best)
So I understand that O is an upper bound and omega is a lower bound. I also understand that case is different than bounds, i.e worst case can have O/Theta/Omega different from best case.
My question: ...
- 11
0
votes
0
answers
57
views
2
votes
1
answer
86
views
Proving the lowest possible time complexity of traversing an array is $O(n)$
How does one go about proving that the lowest possible time complexity for traversing an array is $O(n)$?, it is easy to see that this is the case. But how could I formally prove that this is true?, ...
- 23
1
vote
1
answer
128
views
Algorithm for finding a 'mountain' with the tallest height in O(n) time
Here's the problem:
you get an array of numbers. lets say you get an array of 5 numbers: {5,3,4,1,1}. Each of the numbers in the array represent a 'tower'. Your goal is to make the array in the shape ...
- 11
-1
votes
1
answer
74
views
Why does the big-O for this algorithm not include k?
LeetCode Problem 347. Top K Frequent Elements asks the user to return a list of the $k$ most frequently occurring numbers from a list of numbers. The following solution uses bucket sort:
...
- 45
0
votes
1
answer
101
views
What does weaker term mean in the definition of BigO
I am reading Computer Science Distilled book and in section 2.2 The Big-O Notation there is a line.
A function with fastest-growing term of $2^n$ or weaker is $O(2^n)$
What does weaker mean here? ...
- 208
2
votes
4
answers
330
views
Big O arithmetic of tangent
I haven't seen any estimation with big O of tangent, I tried to use limit for the proof, however for it's oscillating behaviour I find it hard to prove that $tan(x)\neq O(2^x)$ where x is all real ...
- 394
1
vote
2
answers
134
views
Calculating complexity for recursive functions with substitution method (Big O notation)
$$
T(n) = \begin{cases}
4T(\frac n 2) + \Theta(n) & n \gt 1\\
1 & n \le 1
\end{cases}
$$
I have to calculate the complexity of an algorithm taking time according to above equations using ...
- 11
2
votes
0
answers
79
views
Confusion regarding Big-O definition with multiple variables
I've been scouring around looking for a definition for Big-O when you have multiple input variables.
For context, I'm an undergraduate student.
Wikipedia mentions $$f(\mathbf{x})\text{ is }O(g(\mathbf{...
0
votes
1
answer
96
views
Time Complexity of Backtracking solution to Leetcode 473. Matchsticks to Square
The following is a Leetcode problem: 473. Matchsticks to Square (https://leetcode.com/problems/matchsticks-to-square/description/)
Problem Statement
You have an array, matchsticks, of size n, with ...
- 1
0
votes
0
answers
101
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[...
- 101
0
votes
1
answer
57
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 ...
user172436
2
votes
3
answers
237
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 ...
- 31
0
votes
1
answer
91
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+\...
user172436