# Questions tagged [asymptotics]

Questions about asymptotic notations and analysis

1,151 questions
Filter by
Sorted by
Tagged with
0answers
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)$ ...
1answer
42 views

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

I have the following repetition structure: ...
1answer
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 ...
0answers
33 views

0answers
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 ...
0answers
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?
0answers
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 ...
1answer
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 ...
2answers
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))$$
0answers
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)$. ...
0answers
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 ...
0answers
31 views

0answers
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 ...
0answers
34 views

0answers
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 ...
0answers
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 ...
0answers
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 ...
0answers
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 ...
0answers
344 views

### Recursion with loop inside

What is the time complexity of this algorithm? I assume that is $O(3^n)$ ...
0answers
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 <...
1answer
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 ...
1answer
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 ...
0answers
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?!
2answers
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 ...
1answer
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
0answers
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: ...
1answer
552 views

### f(n) and g(n) are monotonically increasing functions. h(n) = max(f,g) => h = O(f) or h = O(g)?

All functions are from naturals to naturals. Let f(n) and g(n) be monotonically increasing functions. prove or disprove h(n) = max(f(n),g(n)) => h = O(f) or h = O(g) I've found close questions ...
1answer
85 views

### is this time complexity subexponential? [duplicate]

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.

1
ā¦
20
21
22 23 24