All Questions
21 questions
0
votes
1
answer
4k
views
If is true f(n) = Θ(g(n)) and if f(n) = o(h(n)) then g(n) = o(h(n))?
In asymptotic notation the transivity holds, however what happens when we have small o such as if f(n)= o(h(n)) does that means that also g(n)=o(h(n)) holds?
i take as granted that both of f(n)=o(h(n))...
- 3
0
votes
0
answers
125
views
Worst case lower bound of the general number guessing problem
I have the following problem:
Let Alice and Bob be two people playing games.
Alice and only Alice owns a special device, Robo, that is capable of generating one truly random number $k \in \mathbb{N}$ ...
7
votes
7
answers
6k
views
Is there a meaningful difference between O(1) and O(log n)?
A computer can only process numbers smaller than say $2^{64}$ in a single operation, so even an $O(1)$ algorithm only takes constant time if $n<2^{64}$. If I somehow had an array of $2^{1000}$ ...
- 171
4
votes
2
answers
305
views
Finding which functions are bounded by $O(n^2)$
I am asked to select the functions that are bounded by the Big-Oh function O(n^2): $f(n) \in O(n^2)$.
$f(n) = \sum_{i=1}^{n} n$
$f(n) = \sum_{i=1}^{n} i$
$f(n) = n + n^2$
$f(n) = 1$
I choose the ...
- 213
0
votes
1
answer
50
views
Need help understanding tightest lower bound ( BigOmega ) of n!
I am currently learning complexity theory and wasn't able to find a tightest lower bound to BigOmega(n!), I am quite certain it isn't n^n and so wasn't able to reach to a tightest lower bound, can log(...
- 219
2
votes
2
answers
1k
views
All superlinear runtime algorithms are asymptotically equivalent to convex function?
Is it true that every algorithm with runtime complexity of $T(n)=\Omega(n)$ satisfies that $T(n)=\Theta(f(n))$ for some convex function $f$?
All the examples that I could think of satisfy the above ...
- 221
0
votes
1
answer
32
views
Sum of a function Θ(g) with a function that is not O(g)
Consider g a function of n: $g(n)$.
Knowing that the function $f(n) \in Θ(g(n))$ and the function $h(n) \notin O(g(n))$, could we conclude anything, related to it's asymptotic behaviour, about $f(n) + ...
- 13
0
votes
1
answer
116
views
Finding the Big-O and Big-Omega bounds of a program
I am asked to select the bounding Big-O and Big-Omega functions of the following program:
...
- 213
1
vote
2
answers
110
views
Lower bound $\Omega$ grows quicker than upper bound $O$ of a recurrence relation $T(n)$?
In my analysis of algorithms class we were given the following recurrence relation:
\begin{eqnarray}
T(n) &=&
\begin{cases}
T\left(\displaystyle\frac{n}{2}\right) + 1, &n \ \mbox{is ...
- 13
7
votes
2
answers
2k
views
Confusion with analysis of hashing with chaining
I was attending a class on analysis of hash tables implemented using chaining, and the professor said that:
In a hash table in which collisions are resolved by
chaining, an search (successful or ...
- 275
0
votes
3
answers
105
views
Is there a unit of measurement that can express code execution speed in absolute terms?
I've always seen code execution speed measured either in units of time (e.g. t milliseconds), or using asymptotic analysis (e.g. O(n log n)). Execution speed will vary depending on hardware ...
- 105
0
votes
0
answers
86
views
Question about asymptotic analysis comparing two functions
I'd be glad for an explanation on the analysis of this exercise. Given these functions: $$f(n) = n^2 \\ g(n) = n^{2/3}$$
Show that $f(n) = O(g(n))$, or $f(n) = \Omega(g(n))$ and comment if $f(n) = \...
- 173
10
votes
2
answers
19k
views
Memory complexity?
I am unclear about finding the memory complexity of an algorithm.
Some places refer memory complexity as what container would be carrying for instance:
...
- 381
3
votes
2
answers
898
views
how to prove that nlogn is not Θ(n) without using limits?
i'm studying an algorithms designing and analysis , and i've question about Big-theta
how can i prove that nlogn is not Θ(n) without using limits ?
- 31
2
votes
1
answer
865
views
Why does every member $f(n) \in \Theta(g(n))$, and $g(n)$ have to be asymptotically non-negative?
The following is an excerpt from CLRS:
The definition of $\Theta (g(n))$ requires that every member $f(n) \in \Theta(g(n))$ be asymptotically nonnegative, that is, that $f(n)$ be nonnegative whenever ...
- 364
6
votes
1
answer
6k
views
Is every algorithm's complexity $\Omega(1)$ and $O(\infty)$?
From what I've read, Big O is the absolute worst ever amount of complexity an algorithm will be given an input. On the side, Big Omega is the best possible efficiency, i.e. lowest complexity.
Can it ...
- 2,977
0
votes
0
answers
37
views
Sum of asymptotic notations
Let's consider a function $f \in \Theta(h)$ and a function $g \in \omega(h)$, what could I conclude about the sum $f + g$?
Since $f \in \Theta(h)$ I think about $f$ as if it grows just like the ...
- 13
2
votes
1
answer
74
views
Complexity Reduction Analysis
I am struggling to grasp fully grasp complexity reductions, I have this example that I am working through and can not fully comprehend how to determine the complexity of one algorithm given the ...
- 71
1
vote
1
answer
65
views
What is the asymptotic time complexity of the following 2 recurrences?
$$T(n) = (\log n) \cdot T(n/\log n) + \Theta(n^i \cdot (\log n)^k)$$
and
$$T(n) = (n\log n) \cdot T(n/\log n) + \Theta(n^i \cdot (\log n)^k)$$
for any given $i$ and $k$.
I think it helps to know ...
- 113
0
votes
1
answer
31
views
Big O analysis trying to follow a logic
Can someone please help me understand why(the derivation) "and m = 2n+1 for each n."?
I am trying to follow the logic of the solution provide while myself have a different approach. Here is my ...
- 227
0
votes
3
answers
443
views
Big O relation between $2^n$ and $2^{2n}$
I know that:
If $f(n) = O(g(n))$ , then there are constants $M$ and $x_0$ , such that
$f(n) <= M*g(n), \forall n > n_0$
The other, plain English way of defining it is,
If $f(n)=O(g(n))$ ...
- 399