Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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 ...