Questions about asymptotic notations and analysis

learn more… | top users | synonyms (2)

2
votes
0answers
21 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
0answers
16 views

What is the Big O of this algorithm? [duplicate]

I'm having trouble working out what the Big O is of this piece of code, any in particular how to analyse it for recursive functions. Could someone explain step by step how to calculate the complexity ...
3
votes
2answers
158 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
51 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
58 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
67 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
23 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
71 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 ...
7
votes
3answers
166 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
70 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
43 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
101 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
68 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
52 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
40 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
53 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
44 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
76 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
356 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
37 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
71 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
49 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
405 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
39 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
33 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
66 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
41 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
129 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
58 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
38 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
194 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
57 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 ...
1
vote
2answers
141 views

Should O(1) necessarily stand for a non-zero constant?

I had a debate with my friend. He argued that $o(1)\subseteq O(1)$, so if a function converges to 0, then it belongs to both $o(1)$ and $O(1)$. However I imagine that $O(1)$ represents a constant ...
6
votes
2answers
488 views

How is this problem related to the study of algorithms and big O notation?

I'm taking a graduate computer science course on algorithms and analysis. The current subject is big O notation and recursion. How is the following problem related to the study of algorithms, ...
3
votes
4answers
57 views

Asymptotic Runtime of Interrelated Functions

I have two functions $S$ and $T$ which are interrelated and I want to find the asymptotic worst case runtime. The fact that they are interrelated is stumping me... How would I find the asymptotic ...
5
votes
3answers
144 views

Finding constants C and k for big-O of fraction of polynomials

I am a teaching assistant on a course for computer science students where we recently talked about big-O notation. For this course I would like to teach the students a general method for finding the ...
-1
votes
2answers
118 views

How to find the cost of pseudocode with a nested loop and a nested if statement?

How can I find the cost of pseudocode with a nested loop and a nested if statement? On the left hand side is an example from a textbook I am following. On the right hand side is pseudo code that I ...
3
votes
1answer
41 views

Recurrence relation in 2 variables

When analyzing an algorithm, the following recurrence relation popped up: $T(n,d)=2T(n/2,d)+T(n,d-1)+O(dn)$ where $T(n,1)=O(n \log{n})$ and $T(1,d)=O(d)$. By applying the Master Theorem ...
2
votes
2answers
163 views

How to deal with questions having two or more asymptotic notations

The following was asked as part of a homework assignment and I am not asking for the solution to these but rather tips or resources on how to solve this and similar questions, Let $f(n)$ and $g(n)$ ...
0
votes
3answers
76 views

Big O relation between $2^n$ and $2^{2n}$

I know that: If $f(n) = O(g(n))$ , then there are constants $M$ and $x_0$ , such that $f(n) <= M*g(n), \forall n > n_0$ The other, plain English way of defining it is, If $f(n)=O(g(n))$ ...
-1
votes
3answers
55 views

Big-Oh question [duplicate]

I am asked to find two functions that are not big-oh of each other. Is it correct if I pick say $f(n)=2sin (n)$ and $g(n)=1$? That way, $f$ will never always be greater than $g$.
1
vote
1answer
195 views

What is the result of multiplying O(n) and Ω(n)?

If $f(x) = \Omega(n)$ and $g(x)= O(n)$, what would be the order of growth of $f(x) \cdot g(x)$ ? First I figured it should $\Theta(n)$ , as two extremes would cancel each other and the order of ...
3
votes
1answer
183 views

Why is log(n/p) asymptotically less than log(n)/log(p)

I'm trying to figure out which is better asymptotic complexity, $O(\log{\frac{n}{p}})$ or $O\left(\frac{\log{n}}{\log{p}}\right)$. $p$ is the amount of parallelism (i.e. number of cores), and $n$ is ...
1
vote
0answers
77 views

Relationshop between Theta and little-o (Big-O notation)

Is $$ f(n) \in \Theta(g(n)) \Leftrightarrow f(n) = g(n) \cdot (1+o(1)) $$ true? For clarity, here are the definitions I use: $$ f(n) \in o(g(n)) \Leftrightarrow \forall \epsilon > 0 \exists ...
3
votes
1answer
50 views

How to solve recurrences involving log?

For example, $T(n) = \log {n} \cdot T(\frac{n}{\log{n}}) + \Theta(n)$ I tried using the substitution method with $ n = 2^m $, but that got me nowhere, since it still ends up with a $m$ and $2^m$. ...
0
votes
1answer
29 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$ ...
1
vote
1answer
26 views

Blum's speedup theorem in big-O format?

Is there a way to state Blum's speedup theorem in terms of Big-O (Landau) notation?