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.
318
questions
1
vote
2
answers
37
views
If we have f(n) ∈ O(h(n)) and g(n) ∈ Ω(h(n)), does that mean that f(n) + g(n) ∈ Θ(h(n))?
It is quite easy to prove that f(n) + g(n) ∈ Ω(h(n)), but I am having trouble with proving/disproving that f(n) + g(n) ∈ O(h(n)).
Someone suggested that this question answers mine, which it doesn't. ...
- 23
1
vote
1
answer
52
views
Placing K gas stations among n cities to minimize distance
There are $n$ cities on a highway with coordinates $x_1$
, . . . , $x_n$ and we aim to build $K < n$ gas stations
to cover these cities. Each gas station has to be built in one of the cities, and ...
0
votes
4
answers
80
views
Is $n^n$ is a big-oh n factorial
Is it true or false that $n^{n} \in \mathcal{O}(n!)$ ?
Any suggestions how to prove/disprove this statement?
- 3
0
votes
1
answer
30
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
2
answers
56
views
If f = O(h) and g = Ω(h) then f+g is?
Is the answer O(h) or Ω(h) for f+g?
My professor says its Ω(h), but I can't get it.
0
votes
2
answers
61
views
Comparison between big-Ω and ω notations
Example of function f(x) such that it is true that f(x) = Ω(g(x)) but that it is not true that f(x) = ω(g(x))
- 111
0
votes
1
answer
36
views
Design an algorithm with linear complexity
Let A[1 : n] be a vector of n integers such that all elements except O(n^2/3) elements are between 1 and 10n. Design an algorithm with linear complexity that sorts A.
Beyond the algorithm, what I can'...
- 111
0
votes
1
answer
44
views
Complexity of recursive function that calls itself with it's own return value
Given the following code:
int f3(int n)
{
if(n <= 2) return 1;
f3(1 + f3(n-2));
return n - 1;
}
I was trying to find the time complexity and I got this ...
0
votes
1
answer
28
views
the size of nice tree decomposition
Recently, I am reading paper An Upper Bound for Resolution Size: Characterization of Tractable SAT Instances, which use tree decomposition to give an upper bound for SAT resolution refutation.
For a ...
- 176
-3
votes
2
answers
74
views
How to find the standard theta notation of this?
Hi i am practising standard theta notation:
How could i find the standard theta notation of the following :
2n + 3n^2(log n)^3 + 2
and
...
- 1
2
votes
1
answer
28
views
Finding general time complexity for recurrence relation $T(n)=aT(n/\alpha)+bT(\beta n/\alpha)+f(n)$
I was given an assignment in which I had multiple recurrence relations and I had to find their Big-oh time complexities. Nearly all of the recurrence relations were of the form as under:
$$T(n)=aT(n/\...
- 121
-1
votes
2
answers
37
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<=...
0
votes
0
answers
41
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
4
answers
78
views
What is the lower bound of n factorial
The upper bound of $n!$ is $O(n^n)$. But I am not getting a way to compute the lower bound of n!.
We can write $n! = n\times(n-1)\times(n-2)\times\dots\times 1$. I can easily put all the terms as 1. ...
- 21
0
votes
2
answers
40
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 ...
- 131
0
votes
3
answers
35
views
Help understanding the proof of the definition of Big-Theta based on limits
I was reading Kleinberg's and Tardo's book (especifically, this one) and, on page 38, these authors define the Big-Theta notation the following way:
Let $f$ and $g$ be two functions that $\lim_{n\to\...
- 3
0
votes
2
answers
59
views
Confusion about asymptotic notations in math and computer science
The last times i was searching a lot to understanding Big O notation or in general asymptotic notations concepts because i didnt hear about it or them before starting studying in computer science.
(...
- 3
0
votes
1
answer
32
views
How can it be formally proved that $f \in O(⌊f ⌋)$
I'm trying to prove that $f \in \mathcal{O}(\lfloor f \rfloor)$ given that $\forall m \in \mathbb{N}, f(m) \geq 1$
Here's what I've thought of so far,
we can set C = 10 and k = 1 and somehow prove ...
1
vote
1
answer
71
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
1
answer
74
views
Proving this recurrence is $n \log n$
I need to prove that $T(n)$ is $\mathcal O(n\log n)$ with the substitution method.
$$ T(n)\leq 3\log n + n + \frac{6}{n}\sum^{2n/3}_{n/3}T(i).$$
This is my attempt: I assume $T(n) \leq c n \log n$ and ...
- 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
0
votes
1
answer
89
views
0
votes
1
answer
36
views
Understanding why this upper bound is tight
Consider an algorithm with the following recursion $$ T(n) \leq T(n/3) + T(2n/3) + \mathcal O(n)$$ for its running time. I understand that $T(n) = \mathcal O(n \log n)$ by drawing the recursion tree ...
- 257
0
votes
2
answers
65
views
Asymptotic Relationship between 1/n and 1/2^n
What is the asymptotic relationship between $\frac{1}{n}$ and $\frac{1}{2^n}$?
The answer here mentions that both functions are $O(1)$ (because they are always $\leq 1$) but not $\Omega(1)$ (because ...
- 11
0
votes
1
answer
141
views
1
vote
1
answer
73
views
Why not $O(n^{\log_ba})$ for case 1 of the Master Theorem instead of $O(n^{(\log_ba) - \epsilon})$?
Someone who was explaining to me the master theorem said that for the case 1, we compare the $n^{\log_b(a)}$ and $f(n)$. If the growth rate of $n^{\log_b(a)}$ is greater than the growth rate of $f(n)$ ...
- 113
1
vote
2
answers
60
views
Asymptotics of $F(n) = n \times n^{\log_32}$
Is the complexity of $F(n) = n \cdot n^{\log_3 2}$ allowed to be written as $O(n)$, or must you specify and say $O(n^{1.63})$, or even must you write $O(n^2)$ since it is an upper bound?
0
votes
0
answers
41
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 ...
11
votes
3
answers
2k
views
Is Big-Theta a more accurate description of worst case run time than Big-O?
Question I was asked: Does it make a difference if I say "The worst case run time is $O(n^2)$ vs the worst case run time is $\Theta(n^2)$?"
To me, the only difference is that when we say $O(...
0
votes
2
answers
70
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
-3
votes
1
answer
55
views
Prove f(n) = o(g(n)) if and only if f(n) = O(g(n)), but f(n) ≠ Θ(g(n))
How can I prove this: f(n) = o(g(n)) if and only if f(n) = O(g(n)), but f(n) ≠ Θ(g(n)) ?
- 1
1
vote
0
answers
39
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
votes
2
answers
326
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
0
votes
1
answer
25
views
Landau Notation/Big O notation
In our class the following exercises/examples were given:
Compute/find $n_0$ and c from the formal definition of each Landau symbol to show that:
$n^{2/3} \in \Omega(log^8(n))$.
Then in the Solution ...
- 185
1
vote
1
answer
36
views
Are there any "fast" algorithms for defragmenting memory?
This is about memory, not files or filesystems.
So in a typical process, imagine you have a string "Hello world" that later gets changed to "Hello". Or a list of 100 objects later ...
- 129
-1
votes
1
answer
75
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, $\...
- 169
0
votes
1
answer
68
views
Complexity of multiple $O(\log N)$ is $m*O(\log N)$ or $O(\log N)$?
Assume we have an algorithm consists of several (assume m and m<10) different algorithms each of which has time complexity $O(\log N)$. Is the time complexity of our algorithm is $m*O(\log N)$ or ...
- 151
0
votes
1
answer
30
views
How to show that $n^2 = O(f(n-1)+n)$?
This is from Ex. 0.2.(b) from "Computational Complexity" by Arora and Barak (2009):
One needs to find a non-recursively defined function $g$ s.t. (1) $f = O(g)$ and (2) $g = O(f)$, where $f(...
- 103
0
votes
0
answers
33
views
Baby step giant step algorithm complexity calculation
My question here is mainly a way for me to understand complexity a little better by a confusing example. From what I understand of calculating the complexity of an algorithm, we take the number of bit ...
0
votes
1
answer
50
views
Big O- and Omega-Notation for functions
I want to find out how to check, if the following relationships are true or false.
f(n) = nlog(n!); g(n) = nlog(2n^3n); Check, if f(n) = O(g(n)) and/or f(n) = Ω(g(n)) true/false;
f(n) = 3n^2; g(n) = 9^...
- 3
1
vote
0
answers
39
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
0
votes
4
answers
68
views
Would someone be able to explain why the Time Complexity here is O(b^d) instead of O(d(b^d))?
So I'm doing an AI course that is talking about time complexities of different tree search algorithms. On this slide it talks about the time complexity of the algorithm, and I'm confused as to why we ...
- 3
0
votes
5
answers
184
views
Prove big O notation for $\log(n!)$ without applying Stirling's formula
I want to prove that,
$$ \log n! \in O(n \log n) \land \log n! \in \Omega(n \log n)$$
The straightforward approach is to apply Stirling's formula but I am looking for a different path to follow.
Can ...
0
votes
2
answers
97
views
Big O notation: how to prove $4\sqrt{n} + 2n\log_2(n) + 3 = \mathcal{O}(n\log(n))$?
I'm following an online course about Complexity and I'm learning a lot of stuff.
I came across a particular exercise and I'm unable to find it out by myself, this is why I'm writing this message here.
...
- 101
-1
votes
1
answer
44
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
0
votes
2
answers
59
views
A little confusion with Big Theta time complexity
I came across one Big Theta expression:
Here I am thinking this expression to be valid. But please correct me as the answer doesn't goes in the same way.
As per definition of Big Theta.. any function ...
1
vote
1
answer
88
views
How to find parameter sets for a big-O expression to be fixed-parameter tractable?
I've been stuck on the following assignment taken from Cognition and Intractability: A Guide to Classical and Parameterized Complexity Analysis:
Imagine that the following big-O expressions ...
- 13
1
vote
3
answers
67
views
Difference between an exact and Big O Notation for worst case runtime
I'm having a problem with an exercise, I'm supposed to calculate the exact worst case runtime and the worst case runtime in Big O Notation for a given algorithm.
This is what I'm struggling to ...
- 13
1
vote
1
answer
643
views
Time complexity when taking certain elements and iterating over them?
I'm trying to gain a better understanding of Big O.
Here is something that I'm unsure about. Say we have an array containing N elements that is inputted by the user. From my understanding iterating ...
- 11
-2
votes
1
answer
51
views
What is the BigO of a C# function when runtime is 3n - logn + 1
I am trying to learn notations for a course and I am stuck on how to even start. I need to figure out the BigO for this function. Question is there's a C# function bool isPalindrome(string S) which ...
- 5