Questions tagged [asymptotics]

Questions about asymptotic notations and analysis

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

Asymptotic calculation check for triple-nested for-loops

I have the following repetition structure: ...
0
votes
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 ...
0
votes
0answers
33 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
25 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 ...
0
votes
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 ...
0
votes
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?
0
votes
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 ...
0
votes
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 ...
0
votes
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))$$
0
votes
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)$. ...
0
votes
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 ...
0
votes
0answers
31 views

Deducing $3^f = o(3^g)$ from $f = o(g)$

I really need help solving the following question: Given: $$f(n) = o(g(n))$$ Prove: $$3^{f(n)} = o(3^{g(n)})$$ My attempt: I know that $\frac{f(n)}{g(n)} \xrightarrow{} 0 $. I need to prove that $f(...
0
votes
1answer
32 views

Trouble finding what this recurrence solves to [duplicate]

I have a recurrence relation of the form $T(n) = 2T(n/2)+O(1)$ I'm not sure how to deal with the big $O$-notation in the problem in order to start solving it ? Any help would be appreciated.
0
votes
0answers
41 views

how to compute $O(n^{0.000001})$ [duplicate]

this MIT course gives a formula about Big O $$n^{0.999999} \log n = O(n^{0.999999} \cdot n^{0.000001})$$ going through wiki, i cannot find a similar Big O properties or usages. how to compute $O(n^{...
0
votes
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 ...
0
votes
0answers
34 views

Minimization with asymptotic assumption

Given the function $g(n,m)=\min\Big\{f(a,b)+f(n-a,c)+f(n,m-bc)\Big|\\a,b,c\ \ \text{with} \left\{\begin{matrix} a,\ b,\ n-a,\ c,\ m-bc \geq 0 \\ b\leq a! \\ c\leq (n-a)! \\ \end{matrix}\right. \Big\}...
0
votes
0answers
36 views

How can I prove the linear time search algorithm takes O(n) time? [duplicate]

The recurrence relation for the algorithm is an eccentric form that has an additional term: $T(n) = T[\frac{n}{2}] + T[\frac{7n}{10} + 6] + n$. Exactly how can I prove that this recurrence relation ...
0
votes
1answer
69 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, ...
0
votes
0answers
22 views

Asymptotic Question [duplicate]

Hi how do I find the asymptotic bound for the recurrence T(n) = T(n/2) + T(n/4) + T(n/8) + n? Can I use master theorem or Substitution method only? If so, I need some help for substitution method. My ...
0
votes
0answers
65 views

Substitution method for $T(n) = 2T(7n/10) + O (1)$ [duplicate]

I want to solve $T(n) = 2T(7n/10) + O (1)$ using the substitution method. I think the solution should be $T(n) = O(n\log n)$, but I am having trouble constructing a proof by substitution.
0
votes
0answers
32 views
0
votes
0answers
28 views

Can the average case of an algorithm be $O(n \log n)$ if the best case running time of an algorithm is $\Theta(n \log n)$? [duplicate]

Let us suppose the best case running time of an algorithm is $\Theta(n \log n)$. Can the average case run time of the algorithm be $O(n \log n)$? Since $O(n\log n)$ would imply the value going even ...
0
votes
0answers
29 views

The applicability of the Master Theorem and calculation of asymptotic limits

Given the following recursive equation $T(n)=3T(\dfrac{n}{8})+ Θ(n^{1/3})$ I want to know how to explain the applicability of the Master theorem in a rigorous way and what means asymtotic limits of ...
0
votes
0answers
23 views

Run time analysis of inner loop [duplicate]

What is the run time of the following piece of code in Big-Oh notation? The first loop runs n times in the worst case. But I am having difficulty in finding run time of nested loop which runs V / deno[...
0
votes
0answers
15 views

Runtime explanation of this function [duplicate]

I am trying to understand the runtime complexity of the below code in terms of n. I know that it is $Θ(n^{4/3})$, but I don't get why. I thought the outer loop runs $log(n)$ times, the second one ...
0
votes
1answer
26 views

Big O analysis trying to follow a logic

Can someone please help me understand why(the derivation) "and m = 2n+1 for each n."? I am trying to follow the logic of the solution provide while myself have a different approach. Here is my ...
0
votes
1answer
3k views

How come O(n) + O(logn) = O(logn)

How come O(n) + O(logn) = O(logn)? When talking for example about an algorithm that has two operations. One of them takes O(n) and the other O(logn) and in the end we say that the total complexity is ...
0
votes
1answer
358 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 ...
0
votes
1answer
173 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
0answers
21 views

Complexity of $T(n) = 4T(n/2) + n^2 \cdot log_2 (n)$ [duplicate]

After constructing the recursion tree i concluded a cost of $n^2\cdot log_2(n)-i\cdot n^2$ per level. So my total cost is: $$\sum_{i=0}^{log_2(n)}n^2\cdot log_2(n)-i\cdot n^2$$ $$=(log_2(n)+1)\cdot ...
0
votes
1answer
221 views

Algorithm Comparison with Theta-notation

We consider two algorithms, Algo1 and Algo2, that solve the same problem. For any input of size n, Algo1 takes time $T_1(n)$ and Algo2 takes time $T_2(n)$. Prove or disprove each of the following ...
0
votes
0answers
24 views

How to solve recurrence T(n) = 5T(n/5) + n/ lgn [duplicate]

It can't be solved with master method. The result seems to be T(n) = Θ (nlg lgn), but I have a problem to prove it. Could you help please?
0
votes
1answer
34 views

Proof of big-o propositions

I don't understand the proof of below sentences. $O(f(n))=O(g(n)) \iff \Omega(f(n))=\Omega(g(n)) \iff \theta(f(n))=\theta(g(n))$ $f(n)=\theta(g(n)) \iff g(n)=\theta(f(n))$ How can I prove these ...
0
votes
0answers
36 views

In what case would bi-directional BFS have the same asymptotic run time as a regular BFS?

I'm not quite sure when they would have the same asymptotic running time. Would it be if the graph was each node connected to one other node in a line? I know that for a bi-directional BFS to have a ...
0
votes
0answers
11 views

Show that x^3 + 5x is not O(x^2) [duplicate]

Below is my solution. Is this sufficient enough to prove? $$|x^3+5x| \le |x^3+5x^3|$$ $$x^3 + 5^x \le 6x^3, x > 1, C=6$$ Let's take $x = 2$. $$f(x) = (2)^3 + 5(2) = 18$$ $$g(x) = 6\cdot 8 = 48$...
0
votes
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 ...
0
votes
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 ...
0
votes
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 ...
0
votes
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 ...
0
votes
0answers
344 views

Recursion with loop inside

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