Questions about asymptotic notations and analysis

learn more… | top users | synonyms (2)

0
votes
0answers
14 views

Not sure if my recurrence is correct for T(n) = 2T(n^.5) + O(1) [duplicate]

I have T(n) = 2T(n^.5) + O(1) = 2(2T(n^.25) + O(1)) + O(1) = 2(2(2T(n^.125) + O(1)) + O(1)) + O(1) and so on To me this seems wrong, and I ...
2
votes
1answer
78 views

Can a Big-Oh time complexity contain more than one variable?

Let us say for instance I am doing string processing that requires some analysis of two strings. I have no given information about what their lengths might end up being, so they come from two distinct ...
0
votes
2answers
61 views

How to simplify the sum over 1/i?

With the recurrence relation: $$ T(n) = 2T\left(\frac{n}{2}\right) + \frac{n}{\log(n)}$$ The "sum for all levels" in the recurrence tree is: $$ \sum_{i=0}^{\log n -1} \frac{n}{\log n - i} = ...
-1
votes
1answer
17 views

Question Concerning Big-O Notation

A couple of questions: When choosing $C$ do I have to choose an integer? I see nothing in my definitions preventing fractions, but I haven't seen any in anything I've looked up, either Given ...
-2
votes
0answers
29 views

confusion regarding big O and small o [duplicate]

I just want this doubt cleared... is Big-O $\supset$ small-o ? Or the fact that in small-o the inequality being valid $\forall$c > 0, leads to small-o being a separate set of functions having an ...
3
votes
2answers
57 views

Origins of misconception about using equality signs with Landau notation

From "Misconception 1" from Søren S. Pedersen's blog, and as many have seen before, a major misconception in Big-O (and others) notation is to say a function is "equal" to Big-O of some other ...
0
votes
1answer
39 views

Showing that tournament sort requrires O(n log n) comparisons

I wish I could think of a better way to word my question. Maybe some one here could offer s suggestion for that, as well. On to my question. Before I do, this is a class question that has been asked, ...
0
votes
0answers
26 views

Asymptotic Complexity of the following two functions [duplicate]

Let $f(n) = n^{1.01}$ $g(n) = n(log(n))^2$ Now I need to figure out whether $f = O(g(n))$ or $\Theta(g(n))$ or $\Omega(g(n))$. I tried taking the ratio $f(n)/g(n)$, apply L'Hospital's rule ...
4
votes
2answers
34 views

What is my error in reasoning about the complexity class $n^{o(1)}$

I'm almost sure I understand $o(1)$ (a class of functions that converge to zero in their limit), but the way I understand it, that would seem to imply that functions in $n^{o(1)}$ converge to 1 (after ...
-3
votes
0answers
31 views

Some Growth Rate of Algorithm Challenge [duplicate]

why from left to right, we have increasing in growth rate? any description for some usual equivalence formula for each of them?
0
votes
1answer
23 views

How do I prove all constants to some exponential power belong to little-o of some function [duplicate]

I'm trying to prove that c2n = o((loglog n)n) (That's little-o) for any constant c. I understand that we can prove one function grows at a smaller rate than the other by taking the limit as n ...
2
votes
1answer
60 views

Which article in front of O(.), Ω(.), …?

Writing a survey, I am confronted to a very difficult and -- I dare say -- deep issue: I have many sentences mentioning or stating results of the form "a $\Omega(\sqrt{n})$ lower bound", or "a ...
0
votes
0answers
29 views

Proof of Asymptotic Fact [duplicate]

I was trying to prove the next exercise 1 It's not look so hard, but with some tries, I couldn't find out a way to show it, I was supposed wrong assumptions. To convince myself if that relation ...
3
votes
3answers
355 views

What is the notation for bounding running time in worst case with concrete example resulting in that worst case running time

I know that Big O is used to bound worst case running time. So an algorithm with running time $O(n^5)$ means its running time in worse case is less than $n^5$ asymptotically. Similarly, one can say ...
0
votes
2answers
55 views

Can we construct a binary tree with width and height Θ(n)?

we know this definition: Given a binary tree, Width of a tree is maximum of widths of all levels. Let us consider the below example tree. ...
1
vote
1answer
39 views

Why are different logarithms in the same Θ even thought their difference diverges?

As I have read in book and also my prof taught me about the asymptotic notations The general idea I got is,when finding asymptotic notation of one function w.r.t other we consider only for very large ...
3
votes
0answers
101 views

Complexity of a naive algorithm for finding the longest Fibonacci substring

Given two symbols $\text{a}$ and $\text{b}$, let's define the $k$-th Fibonacci string as follows: $$ F(k) = \begin{cases} \text{b} &\mbox{if } k = 0 \\ \text{a} &\mbox{if } k = 1 \\ F(k-1) ...
3
votes
2answers
176 views

Can someone clarify landau symbols definition please?

I'm more or less familiar with the landau symbols, most specifically in computer science for complexity, however I was wondering if someone could clarify a bit for me. I'll just mention that I know ...
0
votes
1answer
21 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 ...
1
vote
2answers
61 views

What is the asymptotic behaviour of a sum of powers of three?

I'm more concerned with just finding big oh since that can be used to find big omega. I am also told I cannot use limits to find the answer. I'm given: $3+9+27+\dots+3^n$. My first assumption is that ...
2
votes
1answer
60 views

Use of Big-O Notation: Size of Input vs Input

It is my understanding that, when one is describing time complexity with $\mathcal{O}$, $\mathcal{\Theta}$, and $\mathcal{\Omega}$, one must be careful to provide expressions with regards to the size ...
-2
votes
1answer
73 views

What is the Big O of $2^{\log \log n}$? [duplicate]

What is the Big O class of the following expression: $$2^{\log \log n}$$ I think the Big O is $2^n$ as I assume $\log \log n$ to be $n$. Is my assumption correct?
2
votes
2answers
29 views

Determining Big O [duplicate]

i<--2 while (i<n) someWork (...) i <-- power (i,2) done Given that someWork(...) is an O(n) algorithm, what is the worst case ...
2
votes
2answers
78 views

Is Big-Oh notation preserved under monotonic functions?

I was just looking at the big-Oh notation. I wanted to know if the following is true in general $$f(n)=O(g(n)) \implies \log (f(n)) = O(\log (g(n)))$$ I can prove that this is true if $g$ is ...
8
votes
3answers
174 views

Why doesn't $O(1)+O(2)+\cdots+O(n)$ have an interpretation?

In CLRS (on pages 49-50), what is the meaning of the following statement: $\Sigma_{i=1}^{n} O(i)$ is only a single anonymous function (of $i$), but is not the same as $O(1)+O(2)+\cdots+O(n)$, ...
2
votes
2answers
75 views

Why do we compute time complexity for algorithms? [closed]

I read about Big-O notation with modular arithmetic. So, Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm, where an elementary operation ...
0
votes
1answer
70 views

Time complexity of Dynamic Array via repeated doubling

When we implement dynamic array via repeated doubling (if the current array is full) we simply create a new array that is double the current array size and copy the previous elements and then add the ...
1
vote
1answer
103 views

Analysis of a recursive algorithm, where running time strongly depends on input

I want to find the worst-case running time of an algorithm, which follows the following recurrence equation: The worst-case running time is $\Theta(n^2) + T(n, 2, n)$, where $T(x, i, y) = ...
0
votes
2answers
97 views

Using induction to prove a big O notation [duplicate]

I'm trying to prove that the following recurrence relation has a runtime of O(n): fac(0) = 1 fac(n+1) = (n + 1) * fac(n) ...
3
votes
1answer
59 views

big O of a complex function

I have a complex function, which looks something like this: $$f(x) = \sum_{k=0}^x{\frac{g(k)}{h(k)}} + l(x)$$ Now, $g(k) = O(\log k)$ and $h(k) = O(k)$, the sum iterates $k$ from $0$ to the ...
1
vote
0answers
43 views

Discrete Mathematics books for Computer Science Self-study [closed]

I am an experienced software developer, want to refresh discrete math back in uni. I am looking for a book that is easy to read, contains more examples, and exercises and solutions for self study ...
3
votes
1answer
60 views

Proof or refute $n^n = \Omega(n!)$ with the help of Stirling's approximation

I'm trying to proof/refute the following equation: $$n^n = \Omega(n!)$$ Generally I would try to use Convergence Criteria and or l'Hôpital's rule to solve such a problem. $$\lim_{n\to ...
2
votes
1answer
47 views

Iterated logarithm $\log^* n$

I am to come up with a function based on these premise: Give an example of a function which is $o(\log^k n)$ for any fixed $k$, but which is also $\omega(1)$. The answer is the iterative logarithm ...
0
votes
2answers
80 views

solving recurrence by substitution, calculations doesnt add up

I have this recurrence $p(n) = 2p(n-2) + n$, and I have guessed that the solution is $O(n^2)$, however, when I do the following calculations, I cannot get the inequality to hold $p(n-2) \leq ...
4
votes
2answers
407 views

Solving the recurrence T(n) = 3T(n-2) with iterative method

It's been a while since I had to solve a recurrence and I wanted to make sure I understood the iterative method of solving these problems. Given: $$T(n) = 3T(n-2)$$ My first step was to iteratively ...
-1
votes
1answer
41 views

Is my analysis of this recurrence relation correct?

The following recurrence relation, $$T(n)=16T(\frac{n}{4}) + n^2$$ has been given to me to be solved via the Master Theorem. I'm pretty sure this is a case 2 situation, since $$\log_4{16} = 2$$ and ...
1
vote
1answer
72 views

What order of growth does a ratio of Bigh-Ohs have?

Say that $f(n) = \cal O(n^2)$ and $g(n) = \cal O(n)$. If $h(n)=f(n)/g(n)$, is it true that $h(n) =\cal O(n)$? Is it mathematically correct to say that $h(n) = \cal O(n^2)/ O(n) = O(n)$? if not, ...
1
vote
3answers
51 views

Confusion with the Running Time of an algorithm that finds duplicate character

I have the following simple algorithm to find duplicate characters in a string: ...
0
votes
3answers
412 views

Why is constant always dropped from big O analysis?

Suppose I have an algorithm that has a performance of $O(n + 2)$. Here if n gets really large the 2 becomes insignificant. In this case it's perfectly clear the real performance is $O(n)$. However, ...
2
votes
1answer
40 views

Bounding the recurrence $f(n)=2f(n-1)+2f(n/2)$

I met a recurrence equation for my algorithm $$ f(n) = 2\cdot \left( f(n-1) + f(\frac{n}{2}) \right)$$ with $f(1)=1$, $f(2)=4$, $f(3)=10$. I guess it is $\Theta((2+\epsilon)^n)$, where $\epsilon$ ...
0
votes
2answers
35 views

asymptotic growth of n^log log n [duplicate]

I'm ordering functions by their asymptotic growth for an assignment and I have verified I have the correct order by using limits, but I'm trying to understand why $n^{log\ log\ n}$ is between $n^3$ ...
1
vote
1answer
69 views

find function which is in o(log^k(n)) for fixed value of k and in ω(1) [duplicate]

I need to find a function $f$ which is in $o(\log^{k} n)$ for fixed value of $k$ with $f = \omega(1)$. I know that for little $o$ the function should be strictly less than $c\log^k n$ for all $c$ and ...
2
votes
1answer
49 views

Analysis of Algorithms: Applying Concepts [duplicate]

I believe I understand the concepts of algorithm analysis. However, I'm not fully confident in applying those concepts. I'd appreciate help in bridging the gap between concept and application. I ...
3
votes
3answers
175 views

How do O and Ω relate to worst and best case?

Today we discussed in a lecture a very simple algorithm for finding an element in a sorted array using binary search. We were asked to determine its asymptotic compelxity for an array of $n$ elements. ...
0
votes
0answers
16 views

Iteration method - recurrence [duplicate]

How can I find the tightest possible asymptotic bounds on the recurrence T(n) = 3T(n/2)+cn, where c is a positive constant. Must use iteration method.
3
votes
1answer
58 views

O(f) vs O(f(n))

I first learned about the Big O notation in an intro to Algorithms class. He showed us that function $g \in O(f(n))$ Afterwords in Discrete Math another Professor, without knowing of the first, told ...
3
votes
2answers
61 views

Solve the worst case of this recurrence equation

I am trying to find the worst case $Θ$ bound for the following recurrence equation: $$ T(n)=\sum_{i=1}^kT(a_i)+n+\lg k\sum_{i=1}^ka_i\quad where\quad n=1+\sum_{i=0}^ka_i\quad and\quad a_0\ge a_1, a_2, ...
1
vote
1answer
40 views

Big Oh notation [closed]

I've recently learned about the Big Oh notation and heard that the following aren't true: $f(n)\in O(f(n)^2)$. Either $f(n)\in O(g(n))$ or $f(n)\in\Omega(g(n))$ or both. $f(n)\in\omega(g(n))$ ...
3
votes
4answers
209 views

Why does merge sort run in $O(n^2)$ time?

I have been learning about Big O, Big Omega, and Big Theta. I have been reading many SO questions and answers to get a better understanding of the notations. From my understanding, it seems that Big O ...
-1
votes
1answer
65 views

Examples of algorithms that have runtime O(N + M) resp O(NM)

I'm looking for examples of loops that have running time $O(nm)$, $O(n+m)$ and $O(n\log m)$ to help me understand these concepts. Could anybody give some examples and explain why they have the given ...