Questions about asymptotic notations and analysis

learn more… | top users | synonyms (2)

0
votes
0answers
4 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
67 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
46 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
388 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
37 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
28 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
28 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
34 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
90 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
55 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
56 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
35 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
177 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
44 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 ...
0
votes
0answers
46 views

Amortized Cost of a delete from an extendable heap

Given an extendable heap with $n$ elements and an array size of $A$, I'm trying to use the accounting method to find the amortized cost of a delete. We want a load factor of $\frac{1}{4}$. So, ...
1
vote
2answers
135 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
481 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
53 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
94 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
78 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
37 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
134 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
66 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
51 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
194 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
168 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
58 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
38 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
25 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
22 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?
1
vote
2answers
68 views

How to prove any polynomial of degree $k$ is in $\Theta(n^k)$?

I want to prove that any polynomial of degree $k$ is in $\Theta(n^k)$. The coefficient of $n^k$, $a_{k}$, is positive. I know I need $0 \leq c_{1}n^k \leq a_{k}n^k + ... + a_{0} \leq c_{2}n^k$ for ...
3
votes
2answers
82 views

Which of $e^n$ and $2n^2$ grows faster? [duplicate]

How would you prove/disprove that $e^n = O(2n^2)$? It's unclear to me which function grows faster.
0
votes
1answer
62 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 ...
3
votes
1answer
55 views

Compare asymptotic WC runtime with measured AC runtime

I have an algorithm and I determined the asymptotic worst-case runtime, represented by Landau notation. Let's say $T(n) = O(n^2)$; this is measured in number of operations. But this is the worst ...
2
votes
1answer
46 views

Why does induction with big-O lead to paradoxes? [duplicate]

For example, say I want to analyze $T(n)=3T(\lfloor n/3 \rfloor )+2n$ for $n>2$, and $T(n)=1$ otherwise. This is clearly $O(n\log n)$; however it seems that with induction you can prove it is ...
1
vote
1answer
193 views

Bubble sort complexity

So I have this code: ...
1
vote
1answer
53 views

Runtime analysis of a “find the secret number” algorithm

The algorithm task is to find an integer (range is not known). the function guess(num) returns one of three chars: '>','<' or '='. Find the secret number ...
3
votes
1answer
28 views

Pick parameter function that minimises whole function

I have a recursive algorithm defined by the following recursion. $$T(n) = T(n/f(n)) + O(\log f(n)).$$ I want to find the function $f$ that minimizes $T(n)$. If $f$ is a constant then $T(n) = ...
1
vote
1answer
34 views

Big-O in computer Science [duplicate]

As the title states, I am asking for how the big-O in asymptotic analysis is used in theoretical computer science. It would be helpful if an example would be given.
2
votes
2answers
98 views

Solving the recurrency $T(n) = 2T(\sqrt{n}) + O(1)$ [duplicate]

I need to solve the following recurrency: $T(n) = 2T(\sqrt{n}) + O(1)$. It's for a simple undergrad problem that a student asked me, but I really couldn't solve it. Since it is for an undergrad ...
0
votes
2answers
87 views

Quicksort's asymptotic performance for array of [50,…,50,100,…100]

Let's have an array where first half are of value 50 and the second half 100. What would be the asymptotic performance when sorting using Quicksort. I think it it should be $O(n^2)$ as for array of ...
1
vote
0answers
97 views

Potential values of minimum cost maximum flow algorithm

I have a simple directed graph $G(V,E)$ that has a source $s$ and sink $t$. Each edge $e$ of $G$ has positive integer capacity $c(e)$ and positive integer cost $a(e)$. I am trying to find the minimum ...
4
votes
1answer
44 views

If a one-way functions (OWF) exist, then there exits a OWF that is computable in quadratic running time by a padding argument

I believe this question should be extremely easy but I am having a (embarrassing) hard time figuring out why its true if there exist OWF (computable in polynomial time) then there exits a OWF that is ...
-1
votes
1answer
89 views

how to calculate Average-Case complexity time by using worst-case and best-case complexity time?

For example let's say that we know that the worst-case running time is o(n) and the best-case is o(1). how can i get the average-case running time using the given big Ohs?
1
vote
0answers
115 views

Complexity to find cube root of n [closed]

The cube root of a natural number n is defined as the largest natural number m such that m^3≤n. The complexity of computing the cube root of n (n is represented in binary notation) is (A) O(n) but ...
3
votes
2answers
289 views

What is an asymptotically tight upper bound?

From what I have learned asymptotically tight bound means that it is bound from above and below as in theta notation. But what does asymptotically tight upper bound mean for Big-O notation?
0
votes
1answer
971 views

Selection Sort Time Complexity using Big O notation

I'm trying to understand why the sorting algorithm Selection Sort has a time complexity of O(n^2). Looking at the math, the time complexity is T(n) = (n-1) + (n-2) + ... + 2 + 1 And this is stated ...
6
votes
2answers
105 views

Is there always a Big Oh complexity strictly between any two others?

I'm learning about asymptotic analysis, and have seen some exotic looking complexities living between other common ones. For instance "log log n" is strictly between 1 and log n. It makes me wonder if ...
0
votes
0answers
16 views

Big O notation in a summation [duplicate]

From Introduction to Algorithms(pg 47-49), I need help in understanding the following paragraph: The number of anonymous functions in an expression is understood to be equal to the number of times ...