Questions tagged [asymptotics]

Questions about asymptotic notations and analysis

Filter by
Sorted by
Tagged with
0
votes
1answer
26 views

Growth of exponential functions according to the big O notation

I'm preparing for an exam and trying to make some sense of the growth of the different exponential functions. I picked the trickiest functions for myself and tried to sort them according to the big O ...
11
votes
5answers
2k views

Does it make sense to say Big Theta of 1? Or should we just use Big O?

Does saying $f(x) = \Theta(1)$ provide any extra information over saying $f(x) = O(1)$? Intuitively, nothing grows more slowly than a constant, so there should be no extra information in specifying ...
0
votes
1answer
28 views

Asymptotic calculation check for triple-nested for-loops

I have the following repetition structure: ...
1
vote
0answers
25 views

How to find the asymptotic bit cost

I know from a general point of view what big O notation is. I have taken an algorithms class before that was all implementations and did well. I am now in an algorithms class that is mostly theory and ...
-2
votes
0answers
31 views

Arrange the asymptotic functions according to growth rate

Arrange the following growth rates in the increasing order $$O(n^3),O(1),O(n^2),O(n\log n),O(n^2\log n),Ω(n^{0.5}),Ω(n\log n),\Theta(n^3),\Theta(n^{0.5}) $$ I know how Big O and Theta separately ...
2
votes
2answers
32 views

Select minimal rate of growth

Suppose we have algorithm that is $\Theta(n(t+n^{1/t}))$, where $t>0$ is some parameter. How to select $t$ such that the running time has a minimum rate of growth? Source: Combinatorial ...
2
votes
4answers
100 views

Is this big O notation format correct? $3^n = 2^{(O(n))}$

I am completing a university exercise deciding whether big notations are true or false. I am stuck on this question : $$3^n = 2^{(O(n))}$$ I want to answer False as the format looks incorrect and ...
2
votes
1answer
43 views

Conditions for applying Case 3 of Master theorem

In Introduction to Algorithms, Lemma 4.4 of the proof of the master theorem goes like this. $a\geq1$, $b>1$, $f$ is a nonnegative function defined on exact powers of b. The recurrence relation for $...
1
vote
1answer
87 views

Why is $\log_{2}n = O(n^{0.00001})$? [duplicate]

Why is $\log_{2}n = O(n^{0.00001})$ true? This is obvious to me when the exponent is $> 1$ but i'm having trouble understanding the cases where the exponent is very close to $0$. I would have to ...
2
votes
0answers
26 views

Induction pitfalls with O notation and recursion

I read the following in CLRS 3rd Ed: I'm not sure I understand exactly how to avoid this pitfall. How would one know that the $\mathcal{O}$ notation in this case grows with $n$ and is thus not ...
0
votes
1answer
42 views

How to tackle Big O proofs that involve multiple parameters

I am getting more and more familiar with the whole concept of time complexity but I have never encountered an example where more than one parameter is involved. Therefore, is it possible(well, I am ...
1
vote
2answers
48 views

Proving that $T(n) = T(\lfloor n/2 \rfloor) + T(\lfloor n/4 \rfloor) + T(\lfloor n/8 \rfloor) + n$ is $\in O(n)$

Show $T(n) = T(\lfloor n/2 \rfloor) + T(\lfloor n/4 \rfloor) + T(\lfloor n/8 \rfloor) + n$ is $\in O(n)$. I will make the bound to be $\in O(cn)$ instead. Proof by strong induction. Base case n =1 ...
1
vote
2answers
37 views

Asymptotics of a logarithmic series

Given that, $T(n) = \sum_{i=2}^{n} \log_i n$ I need to find the asymptotic boundary of $T(n)$. Answer given is $\theta(n)$. Please provide explanation.
1
vote
0answers
30 views

Prove that for all functions g: N -> R>=0, and all numbers a in R>=0, if g in Omega(1) then a + g in Theta(g)

Here is a more readable version of the question: Prove that for all functions $g: \mathbb{N}\to\mathbb{R}^{\geq 0}$, and all numbers $a \in \mathbb{R}^{\geq 0}$, if $g \in \Omega(1)$ then $a + g \in \...
0
votes
1answer
68 views

Explanation of O(n2^n) time complexity for powerset generation

I'm working on a problem to generate all powersets of a given set. The algorithm itself is relatively straightforward: ...
1
vote
1answer
33 views

Lower bound for Merge Sort running time

I'm trying to prove that the recurrence $T(n)=2T(\left \lfloor \frac{n}{2} \right \rfloor) + n$ is in $\Omega(n \log_2 n)$. Here's my attempt: Suppose there is some $c>0$ and a positive integer $...
0
votes
0answers
22 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) = \...
0
votes
0answers
16 views

The accounting Method analysis for table expansion by tripleling instead of doubling an array

If we double the array every time we get the amortized cost of 3n or 3$ if you prefer. I was wondering what would it be if we tripled the array size instead of doubling it. The rational between the ...
1
vote
0answers
38 views

Proving asymptotic bounds

I'm confused if the following approach is mathematically correct Suppose I have to prove $(\log n)! > n^a$, where $a$ is a constant I can assume $n = 2^k$ which leads to $k! > c^k$, where $c = ...
-1
votes
1answer
44 views

Solve recurrence with Master Theorem - Polynomially Smaller/Larger

The problem is to solve the recurrence using Master Theorem : $$T(n) = 2T(n/2)+\log_2 {n}$$ My attempt: $$ a=2, b=2, f(n)= \log_2 {n}, g(n)=n^{\log_b{a}}=n $$ I am torn between case 1 & the ...
0
votes
1answer
36 views

Solving a peculiar recurence relation

Given recurrence: $T(n) = T(n^{\frac{1}{a}}) + 1$ where $a,b = \omega(1)$ and $T(b) = 1$ The way I solved is like this (using change of variables method, as mentioned in CLRS): Let $n = 2^k$ $T(...
2
votes
1answer
37 views

minimizing the maximum between a degree of a tree and its height

I'm interested in asymptotically minimizing the maximum between the height of a tree of degree $k$ with $n$ leaves, and $k$. i.e. minimizing $\max(k, \log_kn)$ asymptotically. If I set $k = \frac {\...
1
vote
1answer
35 views

Asymptotic analysis for machine learning algorithms

I wanted to know if it would practical and useful to analyse machine learning algorithms in terms of asymptotic computational complexity. I have noticed this is very uncommon. However, I believe it ...
2
votes
1answer
47 views

Values of k that make this true, $\log^k n \in \Omega(\sqrt n)$

I have seen some algorithms with complexities like $\log^3 n$ and $\sqrt n$. In view of getting a better idea on how to compare these I wanted to know for which values of $k$ does $\log^k n \in \Omega(...
1
vote
0answers
20 views

Circuit depth of computing the continued fractions of a rational number

If you want to convert a rational number into its continued fraction, what is the circuit depth of this process, in terms of the total number of bits of input? I was reading through some notes which ...
0
votes
2answers
61 views

Is the following true? log2(2n) ∈ O(log2(n))?

Is $\log_2(2n) \in O(\log_2(n))$ ? I don't know how to prove whether this is true or false. Any help is appreciated
0
votes
0answers
39 views

Binary Search Complexity

I was reading an article about Binary Search on one of the websites on the internet that someone had linked, can't find the link anymore, but this really is bothering me, and I think I am missing ...
-2
votes
2answers
63 views

prove that log((n^2)!)= o(log((n!)^2))

i have a question - how i can prove that: $\log((n^2)!) =\theta (log((n!)^2))$ i try something like that: $\log((n^2)!) = 2*(log(n)!)=\theta(2*(log(n)!)=\theta(n\ log(n)) $ $\ \theta(log(n!)^2)=\...
1
vote
1answer
51 views

What is the lower bound for the following equation

f(n) = 32n^2 + 17n + 1. The lecture slide says that lower bound can be Omega(n^2) or Omega(n). Some body please guide me why the lower bound can be Omega (n). i know the upper bound which is O(n^2). ...
2
votes
2answers
87 views

Induction proofs in Big-O notation

I'm not sure how go about this question: Prove the following inequality. For a correct proof, we require a value of the constant $c>0$ and an $n \in \mathbb N$, such that $\forall n>N : f(x)<...
3
votes
0answers
22 views

Bit complexity of computing the sign of an expression evaluated at an algebraic number

I have a univariate polynomial $F(t)\in \mathbb{Z}[t]$ of degree $d$ and maximum bitsize of coefficients equal to $\tau$ and $G(t) \in \mathbb{Z}[t]$ of degree $d^2$ and maximum bitsize of ...
2
votes
1answer
93 views

Is $(n^5 + n^7)\in \Omega(n^7)$? Shouldn't it be in $\Omega(n^5)$?

Is $(n^5 + n^7)\in \Omega(n^7)$? Shouldn't it be in $\Omega(n^5)$? I understand Omega to be a "lower bound" on a function. Shouldn't the largest lower bound on the function $n^5 + n^7$ be $n^5$? (...
2
votes
1answer
75 views

Why is the run time with a loop of this structure considered O(log n)

I used the search function and a good amount of google searches, but wasn't able to get a straight answer on how a loop of the form below, is translated to a proper summation where the function ...
0
votes
0answers
25 views

Quick Clarification Question about Time Complexity in CLRS

I'm reading about the Hiring Problem in "Introduction to Algorithms" and read Interviewing has a low cost, say $c_i$, whereas hiring is expensive, costing $c_h$. Letting $m$ be the number of ...
1
vote
1answer
52 views

About Big O properties

Suppose I have something like the following: $f(x) = g(x) + O(x^n)$ And I apply a power $m$ to both sides $f(x)^m = g(x)^m + \cdots + O(x^n)^m$ My question is whether the following is well ...
1
vote
0answers
35 views

Which function grows faster: N Log N or N^(1+ε/√(log N)) [duplicate]

How would you go about solving this problem? I thought about using a limit infinity approach, but got confused and Wolfram Alpha didn't provide any explanation.
2
votes
1answer
69 views

How do I simplify $O\left({n^2}/{\log{\frac{n(n+1)}{2}}}\right)$

I'm not very certain about how to deal with asymptotics when they are in the denominator. For $$O\left(\frac{n^2}{\log{\frac{n(n+1)}{2}}}\right)$$, my intuition tells me that it should be treated in a ...
0
votes
0answers
37 views

Summing big-O-notation

prove or disprove $$\text{If } f(n)=g(n)+h(n), \text{ then } O(f(n)) = O(g(n))+O(h(n)).$$ I have no idea about where to begin. what are the theories which should be used here?
0
votes
1answer
33 views

How does $n^c \lg n, 0<c<1$ compare to other common time complexities

Between what two common time complexities would you place $n^c lg n, 0<c<1$? The following table illustrates the common time complexities. Source: wikipedia
25
votes
2answers
4k views

Understanding of big-O massively improved when I began thinking of orders as sets. How to apply the same approach to big-Theta?

Today I revisited the topic of runtime complexity orders – big-O and big-$\Theta$. I finally fully understood what the formal definition of big-O meant but more importantly I realised that big-O ...
1
vote
1answer
47 views

Why is $T(n)=3T(n/4) + n\log n$ solvable with Master Method but $T(n)=2T(n/2) + n\log n$ is not?

I am having difficulties in understanding why the recurrence $$T(n)=3T(n/4) + n\log n$$ is solvable with Master Method but $$T(n)=2T(n/2) + n\log n$$ isn't? Despite they both look very similar ...
0
votes
1answer
31 views

Big-O notation for the given function whose runtime complexity grows faster than the input

I struggle to determine the runtime complexity of a function I thought of while trying to solve this quiz. The quiz itself goes like this: Write a program to find the n-th ugly number. Ugly numbers ...
1
vote
2answers
45 views

Simplify the asymptotic expressions $O(n^2 + n) + \Omega (n^2 + n \log n)$

How can it be shown that the expression $O(n^2 + n) + \Omega (n^2 + n \log n)$ simplifies to $\Omega (n^2)$? Why is it not $\Theta(n^2)$?
0
votes
2answers
79 views

In Big-O notation, what does it mean for T(n) to be upper bounded by something

I do not have much experience in mathematics but I would really like to grasp Big-O notation on its mathematical level. I already read What does the "big O complexity" of a function mean? ...
7
votes
5answers
189 views

Is $n^{1/\log \log n} = O(1)$?

Is $n^{1/\log \log n} = O(1)$ ? Suppose that $n^{1/\log \log n} = c$ where $c$ is constant. Taking logs of both sides, $$\frac{1}{\log \log n}\log n = \log c.$$ I am not able to spot an error. ...
12
votes
3answers
330 views

Is O((n^2)*log(n)) greater than O(n^(2.5))?

I know that $O(n^2\times \log(n))$ is greater than $O(n^2)$, but is $O(n^2\times \log(n))$ greater than $O(n^{2.5})$?
2
votes
1answer
82 views

Quickly obtaining sums of sets of numbers

We are given a set of $n$ bits, call them $a_1$, $a_2$,...,$a_n$. We are also given a set of $m$ sums, where the sums $s_1$, $s_2$,...,$s_k$,...,$s_m$ are given as sums of some of the bits. For ...
1
vote
2answers
56 views

Summation of asymptotic notation

How can we solve summation of asymptotic notations like given below: $$ \sum_{k=1}^{n-1} O(n). $$
4
votes
1answer
77 views

Asymptotics of $\frac{1}{\log(\frac{2^n}{2^n-1})}$

I am trying to understand the asymptotics of \begin{equation} f(n) = \frac{1}{\log(\frac{2^n}{2^n-1})} \end{equation} In particular, is there some $c \geq 1$ such that $f(n) = O(n^c)$?
1
vote
1answer
27 views

The space complexity of a function that allocates space based on the input value and not size

What is the space complexity of the following hyphotetical function: void function(int n) { int[] array = new int[n]; // allocate array of size n return; } ...

1
2 3 4 5
22