Questions about asymptotic notations and analysis
0
votes
0answers
16 views
Optimizing with diminishing marginal utility
Let $M$ be the integer number of dollars available, and let $P$ be a set of products to buy. Assuming that for each product its marginal utility decreases as you buy more of it. How to find the ...
0
votes
0answers
21 views
Find asymptotic bounds $T(n)=n^2+T(\frac{n}{2})+T(\frac{n}{4})+T(\frac{n}{8})+…+T(\frac{n}{2^k})$
Give the recurrence relation:
$T(n)=n^2+T(\frac{n}{2})+T(\frac{n}{4})+T(\frac{n}{8})+...+T(\frac{n}{2^k})$
($k$ is some constant and assume $n$ is $2^t$ for some $t\in \mathbb{Z}$)
I'm trying to ...
0
votes
0answers
18 views
Solving Recurrence relation using Master Theorem
There is a recurrence relation like
$T(n)=mT(n/2)+cn^2$
To solve this recurrence relation I am using Master Theorem.
As per master theorem here a = m, b = 2, k=2 ,p=0
So $b^k= 2^2 = 4$
Now, ...
0
votes
0answers
40 views
What's the lower bound of the height of an unbalanced recursion tree?
I don't understand what's going on here. People say, longest path should yield an upper bound of tree height while shortest path should yield a lower bound of tree height. Please take a look at https:/...
4
votes
2answers
80 views
Is “super-exponential” a precise definition of algorithmic complexity?
I cannot seem to find a precise definition of what "super-exponential" is supposed to refer to when one's talking about an algorithm's time complexity.
For instance, if an algorithm runs for $nC(n-1)$...
0
votes
1answer
19 views
Showing $2^x$ is a lower bound
How do I show that $2^x - x^2 \in \Omega(2^x)$?
Basically, I know that this means that $\exists a, x_0 \in \mathbb{R^+}, \forall x \in \mathbb{N}, a.2^x \leq 2^x - x^2$.
I worked around a bit with ...
0
votes
1answer
22 views
Big O order of a function
I'm doing some practice questions on Big O notation and came across this question. What is the Big O order of function 𝑓(𝑛) = 𝑛^2 + 𝑛 log2(𝑛) + log2(𝑛). Show your working.
My answer is O(n^2) ...
1
vote
1answer
43 views
How to find sets of polynomially bounded numbers whose subset sums are different?
Let $n$ be any positibe integer and set $N=\{1,\dots,n\}$. Now select two arbitrary but different subsets of $N$, say $S$ and $S'$. We are interested in finding a function $\pi(A)=\sum_{i\in A}a_i$ ...
1
vote
2answers
49 views
Is the runtime of binary search big omega of logarithm of n?
My question is that can we say that runtime of the binary search is $\Omega(\log n)$?
I know it is both $\Omega(1)$ and $O(1)$ for the best case, and $\Omega(\log n)$ and $O(\log n)$ for the worst ...
1
vote
1answer
44 views
Big O and constants [duplicate]
I've already asked this question on stack overflow, but guys have suggested me to ask my question here.
Let's consider classic big O notation definition (proof link):
The $O(f(n))$ is the set of all ...
0
votes
2answers
25 views
Calculation of Inorder Traversal Complexity
I want to analyze complexity of traversing a BST. I directly thought that its complexity as $O(2^n)$ because there are two recursive cases. I mean $T(n) = constants + 2T(n-1)$. However, AFAI research ...
0
votes
0answers
26 views
Big Oh of $(10n + 1)^4$ [duplicate]
I am in the process of finding Big Oh for $(10n + 1)^4$. I decided to set $c = 1$ and $k \approx 10,000.4$ in order to make $(10n + 1)^4 \in O(x^5)$. Is this the correct approach?
Thank you!
1
vote
1answer
17 views
Big-Oh vs Theta in recurrence tree method
I am solving this problem from here.
The given relation is
$$T(n) = 2 T(\frac{n}{2}) + n^2, \, T(1) = 1$$
The solution via recurrence tree method is given as:
The zeroth level has a single node ...
1
vote
1answer
56 views
Asymptotic behavior of $n\sqrt n + n \log n$ & $\log_{100} n$ [duplicate]
I have the following two functions
$f(n) = n\sqrt n + n \log n$
$\log_{100} n$
And I need to classify them into the followings:
$O(n)$, and/or
$O(n^2)$, and/or
$O(n^3)$, and/or
$O(n^{1.5})$, and/or
...
1
vote
2answers
45 views
Big-O Solving Recurrence Relation by iteration with fractions
I was trying to solve the recurrence relation in order to get a some big-O bound $$ B(n) = B(n-4) + \frac{1}{n} + \frac{5}{n^{2} + 6} + \frac{7n^{2}}{3n^{3} + 8}$$ by following the accepted answer ...
1
vote
2answers
71 views
Why is $\dfrac{1}{2}n^2-3n = \Theta(n^2)$?
By definition:
For a given function $g(n)$ we denote by $\Theta(g(n))$ the set functions
$\Theta(g(n))$ = $\{f(n):$ there exists positive constants $c_1, c_2$ and $n_0$ such that $0 \leq c_1g(...
0
votes
0answers
24 views
Does $\lg{(n+1)} \in O(\lg{n})$? [duplicate]
I know this is kind of an ugly notation, so if you prefer: let $f(n) := \lg{(n+1)}$. Does it hold that $f(n) \in O(\lg{n})$?
3
votes
2answers
55 views
Asymptotic growth of $\log(n^n + n)$
I would like to know if my understanding of this is correct:
The question asks to show that the Big-Oh of the following function is $O(n\log(n))$
$$
\log(n^n + n)
$$
I think the first step is to ...
3
votes
3answers
113 views
How can I solve the recurrence $T(n) = 4T(n/2) + n^2\log^2n$? (without master theorem) [duplicate]
I can not find the appropriate variable to change the second part $n^2\mathrm{log}^2n$.
0
votes
1answer
28 views
Why is max{n,k}= Ө(n+k) [duplicate]
I saw this relationship in my exercise.
max{n,k}= Ө(n+k)
Could somebody prove it?
1
vote
2answers
39 views
Is $n^3$ an asymtotically tight bound of $(n^{2.99}).(\log_2n)$? How? [duplicate]
Is $n^3$ an asymtotically tight bound of $(n^{2.99}).(\log_2n)$? If so then how?
1
vote
1answer
16 views
Represent polynomial time complexity as linearythmic
To determine the experimental time complexity of radix sort, I wrote a program that counted the number of steps the algorithm took to sort N points. I ran that program for multiple N length arrays, ...
0
votes
1answer
51 views
Show that $T(2^n) = \Theta(3^n)$ [duplicate]
We have a function $T(n)$ defined by $T(1) =1$ and $T(n)=3T(\lfloor n/2\rfloor)+n$ for $n > 1$. We need to show that $T(2^n)=\Theta (3^n)$. How should I approach this question? Any suggestion?
0
votes
1answer
55 views
Big O Notation Simplification in the fraction form
How should I approach this one a(n) = $\frac{n^3}{log^{3}(n)}$. As We can tell that $n^3$ grow much faster than $log^{3}(3)$. All of sudden, not sure what to do, found this [post][1], which is also ...
1
vote
1answer
57 views
Big-O with nested loops and “variables” in the T(n)
So, I need to find the T(n) and then Big-O (tight upper bound) for the following piece of code:
...
1
vote
1answer
37 views
Introductory explanation of the Big-Oh properties
I've noticed that Big-Oh notation actually has some properties such as summation, product but i couldn't find an introductory explanation for their use or how they can help to solve asymptotic ...
1
vote
2answers
46 views
How to prove $\Theta(g(n))\cup o(g(n))\ne O(g(n))$
How to prove $\Theta(g(n))\cup o(g(n))\ne O(g(n))$ ?
Is there a simple example for understanding? Seems there's a gap between $O(g(n))- \Theta(g(n))$ and $o(g(n))$ just from the definition. But I ...
1
vote
1answer
21 views
Is this correct in term of big-oh notation: given $g = O(f)$ and $h = O(f)$ can we say $g = O(h)$?
We have two equations $g = O(f)$ and $h = O(f)$ , then can we derive that $g = O(h)$.
I came up with following proof but i dont know it's correct or not.
$$g = O(f)$$
$$g \le c_1*f $$
$$h \le c_2*f $$
...
1
vote
1answer
22 views
Asymptotic bound of a heap's height
Today I was taught that since the height of a heap cannot exceed $\log n$, it is $O(\log n)$; height in my class was defined as the maximum number of steps in a simple path from a leaf to the root. ...
1
vote
1answer
26 views
Master theorem recurrence relation
Consider I have the following recurrence
$$T(n) = 10T(n/3) + \Theta(n^2\log^5 n)\,.$$
Now, by the master theorem, if we evaluate $n^{\log_{b}{a}}$, we get $n^{\log_{b}{a}} = n^{\log_{3}{10}} = n^{2....
0
votes
0answers
25 views
Algorithm Fragment Analysis
I am not exactly sure what this question is asking:
Provide an asymptotic notation for the sum obtained as the result of the following program fragment:
...
0
votes
1answer
74 views
what is the time complexity for binary division by repeated subtraction?
The divisor and dividend are of length n and m bits respectively.
According to Wikipedia article,
https://en.wikipedia.org/wiki/Output-sensitive_algorithm
division by substraction is an output ...
1
vote
1answer
37 views
Mathematically calculating time complexity
This is a thread about mathematically calculating time complexity of nonlinear functions. I know that those questions were asked a lot, but it didn't make me understand fully the subject.
Also I ...
1
vote
1answer
21 views
Big-Oh and Growth Rate
So, in the book I'm studying from it says :
The statement “f(n) is O(g(n))” means that the growth rate of f(n) is no more than the growth rate of g(n).
What I understood from this statement is ...
-1
votes
2answers
46 views
What is the Big-O runtime of this algorithm? [duplicate]
Can anyone explain why the runtime of this is in O(N^3)?
Additionally, what would the run-time be in Big-OH if the else statement was removed.
...
0
votes
0answers
40 views
Assympotic analysis
If we have two functions $f(x)$ and $g(x)$, such that $$\lim_{x\to∞} \frac{f(x)}{g(x)} = c$$ for some finite c, then $f(x) = O(g(x))$. Is the opposite true? That is, if $f(x) = O(g(x))$, must it be ...
2
votes
2answers
31 views
Not able to find any pattern for $4T(n/2)+n^2 n^{1/2}$
I have tried my best but I'm not able to find any pattern for the $n^2n^{1/2}$ part. This question must be solved iteratively and I get totally clueless after two iteration.s I've to find tight bound ...
1
vote
2answers
53 views
What does ∈ mean in the exponent?
I'm having troubles understanding the following proof:
$$
\begin{align*}
&\text{Proof: } \forall \epsilon \in \mathbb{R}^+, \forall a \in \mathbb{Z}^+, n^\epsilon \gg \log_a(n) \\
&\...
1
vote
1answer
16 views
Prove that different definitions of big-Oh with n>=1 or n>N are equivalent
I am coming across two slightly different definitions of big-oh and need to prove that they are equivalent to each other:
Definition 1: f(n) = O(g(n)) if there exists constants c and N such that f(n) ...
1
vote
1answer
71 views
Asymptotic Notation Analysis
2^n=O(3^n) : This is true or it is false if n>=0 or if n>=1
since 2^n may or not be element of O(3^n)
I need a hint to figure the problem
3
votes
1answer
64 views
Removing arithmetic within recurrences
A similar question was asked here: Solving recurrences using substitution method, but I am still somewhat hazy as to how this process works.
Say, for $T(n) = T(\lceil n/5 \rceil + 36) + n \log n$
...
3
votes
1answer
59 views
Asymptotic analysis of a summation
I was calculating the time complexity of one of the phases of my proposed algorithm, but unfortunately, I faced a problem about solving that and providing an understandable running-time. This phase of ...
0
votes
1answer
33 views
Exponential nested Loop Big O complexity calculation [duplicate]
Can I get a bit of help over here, I can't seem to get to a finish point with this code complexity. I have trouble with making notations, exponential ones in particular..... I spent hours with this ...
0
votes
1answer
22 views
complexity class of functions [duplicate]
What would these statements mean if f(n) and g(n) are functions over natural numbers?
g(n) is in Θ(f(n)).
and
An algorithm is in the complexity class Θ(f(n)).
1
vote
1answer
51 views
Understanding this explanation about Big O notation
I'm trying to learn the Big O Notation...and I got a bit confused by this article:
https://brilliant.org/practice/big-o-notation-2/?chapter=intro-to-algorithms&pane=1838
where it stands that f(...
2
votes
1answer
23 views
How to solve $T(n)\leq n^2+n\left[T(n-m)+T(m-1)\right]$?
I am trying to find $T(n)=O(f(n))$, where $$T(n)\leq n^2+n\left[T(n-m)+T(m-1)\right],$$ where $m\in\{1,2,\ldots,n\}$.
Is it possible to find $f(n)$ such that $T(n)=O(f(n))$?
I started to fix $m=n/2$...
1
vote
3answers
70 views
Is the capacity of a hash table a constant value?
In this paper, page 4, it is said:
"...there is always a constant expected number of elements that map to the same slot"
Assume we have a set $S$ of $n$ values, and we want to insert them into a ...
1
vote
1answer
38 views
Asymptotic bound of a recursive function
Consider the following procedure computing a dummy function. Which one is a correct asymptotic bound for the running time of F(N) expressed in terms of N?
...
5
votes
2answers
68 views
Big O notation: removing big O from denominator
In A First Course in the Numerical Analysis of Differential Equations (page 26) Arieh Iserles gives the following derivation:
\begin{equation}
\frac{\rho(w)}{\ln(w)}=\frac{\xi+\xi^2}{\xi-\frac{1}{2}\...
4
votes
1answer
51 views
Merge sort worst case running time for lexicographical sorting?
A list of n strings each of length n is being sorted in lexicographical order using the merge sort algorithm. Since we have to take care of comparison of each character in the strings so the merge ...
