Questions tagged [asymptotics]

Questions about asymptotic notations and analysis

Filter by
Sorted by
Tagged with
0
votes
0answers
17 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 ...
3
votes
1answer
45 views

Compare log^k(n) with n^(1/2)

I'm trying to prove or disprove that $\log^{k}(n) \in O(\sqrt{n}), \ \forall k > 0$. By using the free version of wolfram and testing some increasing values of $k$ I get that: $$\lim_{n \...
0
votes
1answer
35 views

Is this computational complexity of the k-NN (custom distance) correct?

I read on a book that in general k-NN (no optimizations), given $d$ dimensions $n$ examples every computation of distance is $O(d)$. Since every example has to be compared with all the other ones, ...
1
vote
1answer
43 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
33 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
61 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
35 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?
2
votes
1answer
63 views

Interpretation of an asymptotic notation

Assume that we measure the complexity of an algorithm (for some problem) by two parameters $n$ and $m$ (where $m \le n$). What is the formal interpretation of the following claim: there is no ...
0
votes
1answer
29 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
2
votes
1answer
81 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 ...
24
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
votes
2answers
277 views

How do I analyze Mergesort that uses Insertion Sort for small inputs?

I know that Insertion Sort is faster when size $N$ is a small number, hence by modifying Merge Sort to use Insertion Sort when size $N$ reaches $K$, can help improve the performance. How do I ...
1
vote
1answer
58 views

Recursion Time Complexity (Half n' Half)

This is my solution for Leetcode 395, and I'm wondering how I can come up with its time complexity: Input: string $s = s_1,\ldots,s_n$, integer $k$ Go over all symbols $s_1,\ldots,s_n$, one by one ...
1
vote
1answer
39 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 ...
4
votes
2answers
247 views

Is there a data structure that can find the kth smallest in constant time with logarithmic add and delete operations?

I'm looking for a single or a conjunction of data structures that can find the kth smallest element in constant time, delete the kth smallest element in logarithmic time, and add a new element in ...
0
votes
1answer
28 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
34 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)$?
7
votes
5answers
183 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. ...
0
votes
1answer
35 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? ...
12
votes
3answers
247 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})$?
20
votes
7answers
3k views

Justification for neglecting constant factors in Big O

Many a times if the complexities are having constants such as 3n, we neglect this constant and say O(n) and not O(3n). I am unable to understand how can we neglect such three fold change? Some thing ...
1
vote
2answers
39 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
76 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
24 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; } ...
2
votes
2answers
56 views

How to determine time complexity with a simple way?

I'm learning about time complexity but all the cases we did in class were rather simple. Now I'm working on my home work and the cases our teacher let us have was: $$f(n) = 4n(n + 2 \log^2 n^2) + e^{−...
35
votes
6answers
10k views

Sorting functions by asymptotic growth

Assume I have a list of functions, for example $\qquad n^{\log \log(n)}, 2^n, n!, n^3, n \ln n, \dots$ How do I sort them asymptotically, i.e. after the relation defined by $\qquad f \leq_O g \...
-2
votes
2answers
75 views

Show that: $0.01n \log n - 2000n+6 = O(n \log n)$

Show that $0.01n \log n - 2000n+6 = O(n \log n)$. Starting from the definition: $O(g(n))=\{f:\mathbb{N}^* \to \mathbb{R}^*_{+} | \exists c \in \mathbb{R}^*_{+}, n_0\in\mathbb{N}^* s. t. f(n) \leq cg(...
2
votes
1answer
55 views

Show that the union of Θ and o is not O

Show that: $\Theta(n\log n)\cup o(n\log n)\neq O(n\log n)$ I tried to start this in many ways but I don't really know how... intuitively isn't $\Theta \cup o = o$? So that would mean that I would ...
0
votes
1answer
36 views

Find function that satisfy the relation

Can you find the function that satisfy the relation? $$f(n) = \Theta(g(n)), f(n) = o(g(n))$$
2
votes
0answers
33 views

Difference Between $n^{\Omega{(1)}}$ and $\Omega{(n)}$ [closed]

I am not sure about the difference between $n^{\Omega(1)}$ and $\Omega(n)$. It seems to me that the only difference is that $n^{\Omega(1)}$ can contain some sublinear functions, i.e., $n^{\frac{1}{2}}$...
2
votes
1answer
45 views

Big theta of function with multiple types of n [duplicate]

I have the following function: $\displaystyle\frac{n \cdot 7^n+\frac{8}{n!}}{(n+7) \cdot 7^n}=\Theta(1)$ I don't how they come to this. What is the proper way to analyse a function to theta notation?...
1
vote
1answer
38 views

Is log(n) equivalent to (log(n))^x for big-O analysis?

My professor noted that we could treat any logarithmic function with an exponent as equivalent to log(n) for the purposes of big-O analysis. ie. $(n log(n) + 1)^2 + (log(n) + 1)(n^2 + 1)$ From the ...
4
votes
1answer
75 views

Solving $T(n) = 2T(n/2) + T(n-1)/\log n$

I am interesting in the asymptotic rate of growth of the following recursion: $$ T(n) = 2T(n/2) + \frac{T(n − 1)}{\log n}, $$ with base case $T(1) = 1$. I'm having trouble of solving this recurrence ...
2
votes
1answer
67 views

When are log complexities considered equivalent?

Would we consider $O(\log_2(n))$ to be the same complexity as $O(\log_2(n-1))$? Why or why not? I'm specifically wondering about how the number we take the log of affects the time complexity.
2
votes
1answer
31 views

Splitting summations?

From CLRS Introduction to Algorithms, Appendix A, page 1152. They discuss a method called "Splitting Summations", where they split the summation and bound each term separately. For example, ...
1
vote
3answers
61 views

How to mathematically prove that a relation T(n)=T($\sqrt{n}$)+c is O(log(log(n))?

following question, I understood the intuition behind how cutting down the size of input by square root on each iteration leads to O(log(log(n))) complexity. I tried to derive it on paper. Let T(n) =...
0
votes
1answer
46 views

Simplifying this expression with big O when several variables are involved

I have an algorithm which depends on three variables an where the running time is in $\mathcal{O}(m+2 m\cdot n\cdot p+p\cdot(n+m))$ and I would like to simplified it. I proceeded as follows : \begin{...
1
vote
1answer
54 views

Is $(\sqrt{n})!=Θ(\sqrt{n}^{\sqrt{n}})$?

I would like to express $(\sqrt{n})!$ in terms of $Θ()$ notation. My approach is the following: $$(\sqrt{n})!=f(n)\Leftrightarrow$$ $$\log(\sqrt{n})!=\log(f(n))$$ Now from Stirling's approximation ...
0
votes
0answers
13 views

Detailed explanation of Perlin Noise algorithmic complexity

I am doing a project in analysis of algorithm and I have been looking all over for something more complex than Perlin Noise is $O(n \cdot 2^n)$ because of the doubling in $n$ dimensions and array ...
4
votes
2answers
199 views

Is asymptotic ordering preserved when taking log of both functions?

In one of my exercise sheets I have the following question; Let $f,g\colon \mathbb{N}\longrightarrow\mathbb{R}$ be positive functions with $f(n) \in O(g(n))$. Prove or disprove; $\ln(f(n)) \in O(\ln(...
2
votes
1answer
43 views

Showing that $n\log n - n$ is $\Omega(n)$

Prove that $n\log{n} − n$ is $\Omega(n)$. I do know the answer: $\log{n} ≥ 2, \forall n \ge 4$. Thus, $n\log{n}−n\ge n ,\forall n\ge 4 \implies n \log n − n ∈ Ω(n)$. But can someone please ...
1
vote
1answer
36 views

What is the difference between Big(O) and small(o) notations in asymptotic analysis? [duplicate]

What is the difference between $O$ (big oh) and $o$ (small oh) notations in asymptotic analysis? Even though I understand that $o$ is used for a bound that is not tight, is it allowed to use $O$ ...
1
vote
1answer
50 views

Why is building a heap $\mathcal O(n)$ and not $\theta(n)$?

From what I see online, all seem to suggest that heapifying takes $\mathcal O (n)$ time, but it seems like it should always takes $\theta(n)$ time, even in the best case. Is something wrong with my ...
0
votes
2answers
110 views

Runtime complexity of a brute force factoring algorithm? (in terms of bits)

Let N be an n bit number. A brute force algorithm factors N by trying to divide N by all of the numbers between 2 and sqrt(N). Given that dividng two n bit integers takes O(n^2) time, what is the ...
2
votes
1answer
54 views

Spotting the difference between two arrays using divide-and-conquer

Say we have two equal-sized arrays that contain a 1 or 0 at each of their indices. These two arrays are identical, except at one unique index. We want to find and output that particular index. For ...
2
votes
0answers
38 views

Why can't we use the Master Theorem on recurrences with floor or ceiling operations? [duplicate]

From my understanding, using such operators on large numbers doesn't have an impact on running time, since the integer rounding becomes negligible after a certain point. For example, the recurrence $$...
2
votes
1answer
42 views

Can we apply the Master Theorem to the following recurrence?

Our recurrence is $$ T(n)= \begin{cases} T(\lfloor{n/2}\rfloor)+(\log(n))^{2}, & \text{if $n>1$} \\ 1 & \text{if $n=1.$} \end{cases} $$ I have identified $a = 1 > 0$, and $b = 2 > 1$...
3
votes
2answers
43 views

How to show that every quadratic, asymptotically nonnegative function $\in \Theta(n^2)$

In the book CLRS the authors say that every quadratic, asymptotically nonnegative function $f(n) = an^2 + bn + c$ is an element of $\Theta(n^2)$. Using the following definition \begin{align*} \...
0
votes
1answer
47 views

Bubble sort: how to calculate amount of comparisons and swaps

For a given sequence 1, N ,2 ,N −1 ,3, N −2, ... I want to calculate the number of comparisons and swaps for bubble sort. How can I accomplish that using $\theta ()$ notation? I would know how to do ...
2
votes
1answer
26 views

Proving that $S_1+S_2 \leq f^{-\omega(1)}$

I am trying to show for every c, there exists $M\text{ such that }(x,y,z)\geq M$ then $S_1(x,y,z) + S_2(x,y,z) \leq ( f (x,y,z))^{-c} $ . For a particular $S_1,S_2,f$. Does it suffice to prove there ...