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.
379 questions
- Bountied 0
- Unanswered
- Frequent
- Score
- Trending
- Week
- Month
- Unanswered (my tags)
1
vote
1
answer
66
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: ...
0
votes
0
answers
52
views
Complexity of Recursive Algorithm
There is the following algorithm:
...
2
votes
1
answer
76
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?, ...
1
vote
1
answer
117
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 ...
-1
votes
1
answer
69
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:
...
0
votes
1
answer
93
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? ...
2
votes
4
answers
316
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 ...
1
vote
2
answers
127
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 ...
2
votes
0
answers
73
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
78
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 ...
0
votes
0
answers
97
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
1
answer
54
views
Recurrence relation simplification
I have initial condition $n_1=2, v_1=1,ドル and the given recurrence relations: $n_{i+1}=2n_i,$ $v_{i+1}=2v_i+\frac{1}{2} n_i$
I need to show that that,
$v_i=\Theta(n_i\log n_i).$
I observe ...
user avatar
user172436
2
votes
3
answers
221
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 ...
0
votes
1
answer
88
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+\...
user avatar
user172436
1
vote
1
answer
83
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 $...