Questions about asymptotic notations and analysis

learn more… | top users | synonyms (2)

0
votes
0answers
22 views

How to calculate runtime for FOR and WHILE loops? [duplicate]

While there have been many questions/answers around this on stackoverflow and wikipedia, I would like to have a clearer understanding on how to calculate it in layman's terms. I will say that, yes, ...
1
vote
2answers
40 views

Simplifying an upper O-bound in two variables

I have an algorithm that depends on two input sizes n and m. The complexity breaks down to the following equation: $\frac{nm - 1}{n-1} = O(?)$ Is Big-O of the Formula $O(mn)$ or $O(m)$ because $n$ ...
0
votes
0answers
21 views

Landau bounds of a polynomial [duplicate]

I have this question in my homework. Its an a multiple choice question and goes as following: Let $f (x) = 3x^3 + 2x + 4$. One has that $O(x^3)$ ** the answers have been checked with the teachers ...
0
votes
1answer
20 views

Binary tree algorithm asymptotic analysis problem

Assume we have a perfectly balanced Binary tree. We have the following algorithm: For each passed node, traverse through all its ancestors and then do the same algorithm for the left and right child ...
3
votes
1answer
34 views

About a step in the analysis of Quicksort by Sedgewick and Wayne [duplicate]

In the book Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne, when they are analyzing quicksort (page 294), they present the sequence of transformations: $$\begin{gather*} C_N = N + 1 + ...
7
votes
2answers
250 views

n log n = c. What are some good approximations of this?

I am currently looking into Big O notation and computational complexity. Problem 1.1 in CLRS asks what seems a basic question, which is to get an intuition about how different algorithmic ...
1
vote
3answers
218 views

If recursive Fibonacci is $O(2^N)$ then why do I get 15 calls for N=5?

I learned that recursive Fibonacci is $O(2^N)$. However, when I implement it and print out the recursive calls that were made, I only get 15 calls for N=5. What I am missing? Should it not be 32 or ...
1
vote
1answer
104 views

What is the best complexity of finding a minimum in a matrix?

Given a matrix $\mathsf{a}$ of size $K\times N$, what is the best complexity of finding the minimum value? Here is a pseudo code: ...
5
votes
2answers
93 views

How to compare the time-complexity of an optimized algorithm with that of the original?

I had an algorithm with time-complexity of $O(h\times w)$, knowing $h$ is the height and $w$ is the width of an image being processed (or a simple matrix of size $h\times w$). I managed to reduce the ...
3
votes
2answers
88 views

Combining these two results into one asymptotic notation

Assume you have two parameters, $N \gg 1$ and $\epsilon < 1$. I have an algorithm (and matching lower bounds) that runs in $\Theta(\epsilon^{-1}+\log N)$ for $\epsilon > N^{-1}$, and ...
3
votes
2answers
257 views

Landau notation for functions whose limit is 1 (should big-Oh or big-Omega be used?)

I am working on an algorithm which approximates a certain optimal quantity. The approximation becomes better when the size of the problem ($n$) becomes larger: the difference from the optimum is ...
2
votes
3answers
70 views

Notation for asymptotic bounds on both sides

I am writing my first paper, and one of the results can be written as follows: For any $W,\epsilon$ such that $\epsilon = o\left(\frac{\log^4 W}{W\log\log W}\right)$ and ...
1
vote
2answers
44 views

Difference between $F(n)=O(n)$ and $F(n)\le O(n)$?

In a research paper I read $F(n) \leq O(g(n))$ and $F(n) \geq \Omega(h(n))$. Isn't this the same as $F(n) = O(g(n))$ and $F(n) = \Omega(h(n))$? Is there a difference?
0
votes
1answer
21 views

Given asymptotic bounds, what can we say about small n?

I am trying to wrap my head around these asymptotic notations. Given $f(n)$ and $g(n)$, one can write $f(n) = \Omega(g(n))$ as shorthand for $f(n) \geq c*g(n), n\geq n_0$. But what happens when ...
5
votes
1answer
60 views

What is the name for the complexity class $O(n^{1+\epsilon})$

Sometimes problems can be solved in $O(n^c)$ time for any $c > 1$, but not for $c=1$. Typically this is written as $O(n^{1 + \epsilon})$, since $\epsilon$ is understood to be some small positive ...
2
votes
1answer
32 views

How to interpret these asymptotic runtime bounds for discrete logarithm algorithms?

I am trying to compare asymptotic runtime bounds of a few algorithms presented in this research paper, A quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic. ...
0
votes
0answers
12 views

Big notation of sigma 4i (from i = 1 to n) [duplicate]

Why is the big O of this function O(n^2)? Isn't this just a sum of constant terms? Shouldn't the function be O(1)?
0
votes
0answers
11 views

Big O of this function logn + log((n^3) + 1) [duplicate]

I did max(logn , log((n^3) + 1) ) = O(log((n^3) +1)). May I get verification is correct or not? log(n^3) is a worser algorithm than logn because n^3 grows faster than n.
1
vote
1answer
36 views

If f(n) = O(g(n)), then is log(f(n)) = O(log(g(n)))?

I guess this is true, because log is a strictly increasing function, but how do I prove it formally? I tried something like: Let $f(n)$ and $g(n)$ be monotonically increasing functions, $c \in ...
3
votes
1answer
26 views

How to state that a complexity bound does not depend on a given parameter size?

I am often ill at ease with Landau (Big O) notation, because it seems often to be abusing mathematical notation. The best example is the use of the equal sign to express a set membership. And this can ...
0
votes
1answer
24 views

Proving that f(N) = N lg N + O(N) implies f(N) = Θ(NlogN)

How do you prove the following? $$f(N)=N\space lg\space N + O(N) \implies f(N) = \Theta(N \space log \space N)$$ Here $lg\space N \equiv log_2\space N$, and $O$ stands for the big-O, and $\Theta$ ...
2
votes
1answer
183 views

Mergesort with $O(n^2 \log n)$ runtime

I have a task where i need to find a problem in which mergesort has to have a runtime of $O(n^2 \log n)$. In our lecture we said that the runtime is $O(n \log n)$ assuming that every comparison is ...
-6
votes
1answer
57 views

How to solve complexity problems [duplicate]

I have a problem in algorithm subject.. I have to decide whether 127n^2+n^3−4745n^2 is Ω(n^2) or not. How can I do this? Thanks very much!
2
votes
1answer
45 views

Why is f(n) of class O(g(n)) in this graph?

There is a lot of explanation about big O, but I'm really confused about this part. Acoording to the definition of Big-O, in this function $$f (n) \le c g(n), \quad \text{for } n \ge n_0$$ $f (n)$ ...
2
votes
1answer
29 views

Big Theta Proof: May I chose any constant?

I have the following assignment: Prove that $\sum^n_{i=1} i2^i \in \Theta(n2^n)$ My current approach thus far is the following: Since we need to prove $k_1 \cdot n2^n \le \sum^n_{i=1} i2^i \le ...
-1
votes
1answer
44 views

O(2^n) runs in P… Is this true? [duplicate]

My professor doesn't always know what's actually correct or wrong - he always has to think about it for a very long time and get back to the book and read the book for a long time to answer any of our ...
1
vote
2answers
68 views

Complexity of an algorithm

I tried to solve the following exercise : What is the order of growth of the worst case running time of the following code fragment as a function of N? ...
0
votes
1answer
36 views

What is the importance of C in big-Oh notation?

From the definition of Big Oh, it states that there should be a function $g(x)$ such that it is always greater than or equal to $f(x)$. Or $f(x) \le cg(n)$ for all values of $n > n_0$. What I'm not ...
0
votes
0answers
17 views

Master Theorem applied to recurrence relations [duplicate]

Can anyone explain how to use the master theorem to the following problem... $$T(n) = T(\frac{n}{3}) + \log(n)$$
0
votes
1answer
73 views

T(n/3) + log(n)

how do you find the Theta of this problem... $$T(n) = T(\frac{n}{3}) + \log_2(n)$$ I end up getting a pattern of $$T(\frac{n}{3^{k}}) + \log_2(\frac{n}{3^{k-1}}) + \log_2(\frac{n}{3^{k-2}}) + ... + ...
1
vote
1answer
31 views

Recurrence relation chip and conquer

Can anyone explain how to find the $\Theta()$ of this equation... $$T(n) = 3T(n-4) + cn$$ When I solve this problem I get this using the $k$ -th iteration... $$T(n) = 3^{k}T(n-4k) + 3^{k-1}c(n-2(k-1)) ...
2
votes
0answers
20 views

Asymptotic of interesting recurrence relation [duplicate]

I want to study the asymptotic behavior of the following recurrence relation: $y_1=1$; $y_{n+1}=y_{n}+(1+\frac{y_n}{n})^{-n}\ \ $ for $n\ge 1$. I made an initial attempt and guessed that $y_{n} ...
3
votes
0answers
24 views

A totally-ordered set of functions

When we analyze algorithms using the $O$ notation, we usually use only a small set of the space of all functions. E.g., we use $\Theta(n)$ but not $\Theta(2n)$, as these two are equally well ...
4
votes
1answer
56 views

Which bound is better, a logarithmic or a polynomial with arbitrarily small degree?

I have a randomized approximation algorithm which can be tuned by selecting the randomization probabilities. I found out that: For any $\epsilon >0$, there are probabilities for which the ...
4
votes
1answer
770 views

Do not understand why log n = O(n^c) (for any c>0) [duplicate]

Can anyone help me understand this equation? $\log (n) = O(n^c)$ (for any $c>0$) Does it mean that $O(\log (n)) < O(n^c)$ (for any $c>0$)? Added: Please also prove that $\log (n) = ...
1
vote
0answers
84 views

Minimum-Maximum recursive algorithm with a non-even partition, complexity [closed]

So I have been trying to find the recurrence relation of the following algorithm in order to compute its complexity. The following algorithm describes how to find the minimum-maximum element in an ...
0
votes
1answer
31 views

Question about big O notation for function

I'm just starting to learn Big O Notation and I was trying to understand how this function would scale: $\frac{n(n-3)}{4}$ If the function was $n^2$, it would be quadratic, so O(n^2). However, the ...
3
votes
1answer
41 views

Are there algorithms with non-convex and non-concave computational complexity?

If I am not mistaken, an algorithm that runs in time $\Theta(f(n))$ also runs in $\Theta(f(n) + a\sin(bn))$ where $a,b$ are conveniently chosen constants. Therefore I believe that the computational ...
0
votes
0answers
13 views

runtime-analysis, runtime of this equation [duplicate]

Recurrence relation How can I determine the theta of this equation ? T(n)=3T(n/3)+3^(n/3) ,T(i) = 0 if i <0 My teacher gave me this clue : 2<=i<=log(base3)(n) and : for n>50 3^( ...
2
votes
2answers
42 views

Understanding an upper bound in the analysis of Karger's algorithm

I'm reading the wiki page of Karger's algorithm for a self-study of CLRS to get some and I'm confused by one of the bounds they have. Here, under the section about finding all min cuts, they have ...
0
votes
0answers
16 views

State its rate of growth using Θ notation [duplicate]

I have some questions about Analysis of Algorithm Efficiency.Actually, I didn't really understand the theories of this. Please help me to get it guys. My excercise : For each of the following six ...
1
vote
0answers
54 views

Pick algorithm with runtime in O(n) vs. Θ(n) vs. Ω(\log n )

You are given three algorithms, $A$, $B$, and $C$ with the following time complexities in the worst case $O(n)$, $\Theta(n)$, and $\Omega(\log n )$, respectively. Assume that you have to ...
1
vote
0answers
51 views

Why does $\sum\limits_{i=0}^{\lg(n)-1} \theta(\frac{n}{2^i}) = \theta(n\lg(n))$?

I'm reading a proof on the time complexity of MergeSort which makes this statement without any justification. I've tried to show it myself but I'm not getting far; these are my steps so far. ...
2
votes
1answer
22 views

When can we assuredly say that a function is little o of some other function? [duplicate]

I'm trying to determine a function $f(x)$ that is $O(f)$ but not $o(f)$ and also not $\Omega(f)$. Note the $f$ used in the asymptotic notation is not the same as $f(x)$. Originally I thought of ...
-1
votes
1answer
35 views

Little-o notation [duplicate]

Can anyone help me demonstrate these two statements? $$ n! = o(n/2)^n $$ $$ n! = o(n/3)^n $$ I am sure about the first one but I don't know how to demonstrate it. As for the second one I am not ...
-4
votes
2answers
101 views

How long would it take a computer with twice the processing power to solve a polynomial time problem?

Say I have some problem of $O\left(n^k\right)$ complexity. If I were to solve the problem on a computer $x$, it would take time $t$. Now I have a new computer $x'$, which has double the computing ...
3
votes
1answer
55 views

When is the big-O relation preserved under exponentiation?

Suppose that $f, g$ are functions from the positive integers to the positive reals. Under what circumstances will $\log f(n)=O(\log g(n))$ imply $f(n)=O(g(n))$? It's easy to see that this isn't ...
-1
votes
1answer
42 views

Big O notation and functions [duplicate]

$$ f_1(n) = n^2 $$ $$ f_2(n) = n^2 + 1000n $$ Are the following statements true or false? $$ f_1(n) = O (f_2(n)), $$ $$ f_2(n) = O (f_1(n)), $$ Based on what I know about big O notation, I think the ...
0
votes
1answer
28 views

Problem with Understanding a Recursion Tree

Consider the recursion tree: $T(p) = 3T(\frac{2p}{8}) + 2T(\frac{p}{8}) + O(p)$. I determined that there are at most $1 + log_{4}\ p$ levels, because the longest simple path from root to leaf is $p ...
2
votes
1answer
78 views

How to find witnesses for big O

I'm having trouble determining the correct way (if there is one) to find the witnesses in any given big O problem. The example I'm struggling with: $2^x + 17$ is $O(3^x)$. I am expected to find two ...