Questions tagged [asymptotics]

Questions about asymptotic notations and analysis

Filter by
Sorted by
Tagged with
0
votes
2answers
375 views

Are there any exponential-time iterative algorithms?

Is it possible to implement an exponential-time algorithm using iteration, as opposed to recursion? I didn't have any particular algorithm in mind, I was just thinking theoretically. The way I was ...
0
votes
1answer
168 views

Comparing Big O Complexity [duplicate]

I'm trying to compare two functions, such as f(n)=n^n and g(n)=n^10^10. I'm unsure if f(n) is O(g(n)) or vise-vera where g(n) is O(f(n)). From my understanding, n^n can be worse than n! and although g(...
0
votes
1answer
60 views

How to bound a running time equation? [duplicate]

I simply need a standard way to find the upper and lower bound of a running time equation (please no shortcuts that only work for this specific problem).... Example: $T(n)=\frac{c}{5}(4^{\left \...
0
votes
1answer
37 views

How to analyse the complexity of a problem with two or more size measures

Consider this example: a problem of dimension $n$ and $m$ ($m,n$: any given integers). has a search space of size $O(n^n * m^n)$. It is clear that this problem is exponential in $n$, whatsoever $m$ ...
0
votes
1answer
102 views

How to prove that $2^{n+3} = O(2^n)$?

I am a little confused on how to prove/disprove Big O. For the problem, $2^{n+3}= O(2^n)$, I did the following: $$2^{n+3} \leq K \times 2^n$$ Set $K = 1$ $$2^{n+3} \leq 2^n$$ Test for large ...
0
votes
1answer
54 views

Correctness of asymptotic expression from exact expression [closed]

I have the expression: \begin{equation} |Q|f(n)|\Gamma|^{f(n)} \end{equation} Here is my solution to convert the above into an asymptotic expression: $|Q| = 2^l$ for some $l\in\mathbb{R}$ $|\Gamma| ...
0
votes
1answer
45 views

What is growth of $\psi_q(m) = \min \{ p: m ∣ (q^p−1) \}$ for fixed $q$?

I have to estimate the computational complexity of some algorithm that does $\psi_q(m)$ iterations. Assume that all inputs $m$ are coprime to $q$. So I need to know what growth the $\psi(m)$ has.
0
votes
0answers
43 views

Big $O$ approximation for $T(n)=T(n-i)+T(n-(\frac{n}{m}-i))$

I have the following complexity equation: $T(n)=T(n-i)+T(n-(\frac{n}{m}-i))$ with the base case $T(m)=1$. Is it possible to calculate a big $O$ approximation for such equation? What is the right ...
0
votes
1answer
26 views

What is the upper and lower bound for $T(n) = T(\sqrt{n}) +3$, assuming that $T(n)$ is a constant for $n\leq 10$

By unrolling the recursion, \begin{equation*} \begin{split} T(n) &= T(\sqrt{n}) + 3 = T(n^{\frac{1}{2}}) + 3 \\ &= (T(n^{\frac{1}{4}})+3) +3 = T(n^{\frac{1}{4}}) +6 \\ &= (T(n^...
0
votes
1answer
36 views

Asymptotic complexity of Combination sum problem vs Coin change problem

I've been looking at the following combination sum problem: ...
0
votes
0answers
15 views

Is the usage for asymptotic notation for these algorithms correct? [duplicate]

So after reading a lot of information around asymptotic analysis of algorithms and the use of Big O / Big Ω and Θ, I'm trying to grasp how to utilise this in the best way when representing algorithms ...
0
votes
0answers
14 views

Complexity simplification for complexity that consists of partial multiplication

For the algorithm that I have written the complexity is something like: a * e(A) + b * e(B) + b * e(C) + ... Where a represents the instance count of some node A and e(A) the edges outgoing of node ...
0
votes
0answers
30 views

Asymptotics of reccurence relation

I need to tell whether $\quad\exists a \quad T(n) = \omega(n^2)$ $T(n) = T(\frac{n}{2}) + aT(\frac{n}{4}) + n^2\\\\ \forall n<10 \quad T(n) = 1$ And if there is such $a$ I need to find the ...
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
32 views

Asymptotic calculation check for triple-nested for-loops

I have the following repetition structure: ...
0
votes
1answer
53 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
26 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
21 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
42 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
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
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
174 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
47 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
12 views

Growth of n/logn vs n^(1+e) [duplicate]

Is $\Theta(\frac{n}{log(n)})$ faster growing function than $\Theta(n^{1+\epsilon})$, where $\epsilon > 0$?
0
votes
0answers
30 views

Time complexity of simple function related to bits

I am wondering about correct answer to this task from a yesterday's test: A function Pow which calculates $y = a^k$ is given, where $k$ is an integer of length ...
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
26 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
15 views

Mapping every character to its next occurrence based on the number of unique characters between the occurrences

To optimize my LF mapping, I was asked to do the following. Given a string, say $abaxyxwxbx$ I need to encode it in a way where every index stores the value of the number of unique characters ...
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
40 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
33 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
56 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
43 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
25 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
2k 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
317 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
159 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
201 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
31 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 ...