# Questions tagged [asymptotics]

Questions about asymptotic notations and analysis

1,151 questions
Filter by
Sorted by
Tagged with
33 views

### Big O notation of $\left(\begin{array}{c} n\\ \frac{n}{2} \end{array} \right)$

What is the O-notation (or $\Theta$ notation ) of $\left(\begin{array}{c} n\\ \frac{n}{2} \end{array} \right)$ ? Can I use Sterling approximation : $n! = \Theta(\sqrt{n}\left(\frac{n}{e}\right)^n)$ ...
42 views

### Asymptotic calculation check for triple-nested for-loops

I have the following repetition structure: ...
54 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 ...
33 views

43 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 ...
39 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?
21 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 ...
245 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 ...
59 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))$$
75 views

### How to justify $f(n) = O(g(n))$ [duplicate]

The following question is in my homework: Is the statement $f(n) = O(g(n))$ true, when $f(n) = n/2 + 4$ and $g(n) = \sqrt{n} + 2\log_2 n + 3$? I understand how $f(n)$ is the upper bound of $g(n)$. ...
27 views

### Asymptotics and logarithms/exponents

We have four categories: additive constants, multiplicative constants, polynomials, and exponentials When determining the growth order of functions, we only care about polynomials and ...
31 views

26 views

### Calculating the Complexity of a Two Part Algorithm

This is in relation to this post I made. I eventually solved this by the following approach: Take the un-ordered file with all the purchasing data and use the UNIX ...
34 views

128 views

### If $f(n)=\omega(h(n))$ and $g(n)=o(h(n))$ then is $f(n)=\Theta(g(n))$?

My question is exactly what the title says. If I have that $f(n)=\omega(h(n))$ and $g(n)=o(h(n))$ hold, then does $f(n)=\Theta(g(n))$ hold as well? My intuition says that the second part is false, but ...
419 views

### How to find lower bound of f(n) for master theorem

I'm studying the master method to solving a recurrence. It describes three cases, the last one of which depends on what lower bound a function f(n) has. I usually ...
108 views

### Big O Notation for Return List is it O(N)?

what is the Big O for Returning List? aka return list (e.g. list=[1,2,...]) is it o(1) or o(n) and is there a good website for average big o for different operations including sorting for simple ...
24 views

### Ordering functions by growth [duplicate]

I was asked to sort several functions by their asymptotic growth. I was docked a couple points for incorrect ordering and the correct solution was never provided. For what it's worth, this assignment ...
344 views

### Recursion with loop inside

What is the time complexity of this algorithm? I assume that is $O(3^n)$ ...
34 views

### Proving n^2 = O(log n) [duplicate]

This is how I would think it n^2 = O(log n) f(n) <= c*g(n) should c=1 ? n0 = 1 n^2 <= log n 0 <= log n - n^2, for all n>=1 we take n=1 then 0 <= log(1) - 1^2 0 <= 0 - 1 0 <...
562 views

### What is the time complexity of this Factorization program?

input: n-bit integer X output: list of prime factors and their multiplicity acc = X ...
3k views

### What is the difference between a tight Big $O$ bound, a tight Big $\Omega$ bound and a Big $\Theta$ bound? [duplicate]

I occasionally see these terms used and I'm not really sure what is meant by all of them. Is it possible for an asymptotic bound that is not Big $\Theta$ bound to be "tight"? What does it mean for ...
53 views

### What is the Time Complexity of $T(N)=2T(N/2)+\log n!$ and the answer does not have $\log n!$ in it? [duplicate]

None of the 4 possible answers have $\log n!$ in them e.g. one of them is $O(n\log n)$ I tried solving, but I can't get why there is no $\log n!$ in non of the answers?!
92 views

### Similarly structured loops with different big-O time complexities?

I have a function: int sum = 0; for (int i = 1; i < n; i*= 2) for (int j = 0; j < n; j++) sum++; From my understanding this is $O(n\log(n))$ because ...
78 views

### What is the time complexity of the following loop? [duplicate]

function (n) i = 1 s = 1 while (s <= n) i = i+1 s = s*i print "*" end
275 views

### Run time analysis of a program with nested for loops

Problem Let's say we are given a program and we want to find an algorithm that analyses its asymptotic complexity. This program can only have two types of statements: ...
Is next time complexity sub-exponential? $O(2^{N^{LOG2(1.5)}}/8)$ unformatted: O((2^N)^LOG2(1.5))/8) just in case I didn't format it properly.