Questions about asymptotic notations and analysis

learn more… | top users | synonyms (2)

2
votes
1answer
25 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
37 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
46 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
30 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
55 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
25 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
21 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
52 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 ...
-1
votes
0answers
29 views

Algorithmic Complexity Big O, Little O, Big Omega, Little Omega, Theta [duplicate]

Here's the question I'm working with For each pair of expressions, indicate whether A is O, o, Ω, ω, or Θ of B. I understand is pretty much the upper bound and omega is the lower bound and theta is ...
4
votes
1answer
724 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
37 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
20 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
35 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
12 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
34 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 ...
-2
votes
0answers
17 views

Big Omega proof $4n^3 \in\Omega(n^2)$ [duplicate]

Prove or disprove, find a $C$ and $n_0$ if appropriate $4n^3\in\Omega(n^2)$. I've never really understood how to prove these types of problems or how to prove them. I am looking for a $n_0$ and $C$ ...
1
vote
0answers
50 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
49 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
34 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
87 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
47 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
38 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
25 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
39 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 ...
0
votes
2answers
43 views

Why does the Θ-class survive adding a constant only for positive, monotonic, and non-decreasing functions?

I know that for positive monotonically non-decreasing functions, f(n) and g(n), f(n) = O(g(n) + c) entails f (n) = O(g(n)) Why is this always true only for ...
0
votes
1answer
105 views

Example of worst case input for Build-Max-Heap

Is there a worst-case inputs for Build-Max-Heap? I know there is but I just couldn't paint a clear picture of it in my head.
1
vote
1answer
40 views

Use of Big-Oh in Worst case [duplicate]

If it is given that a program has a worst case running time of $O(n)$, then is it still okay to define the running time as being $O(n^2)$. By definition, this seems corrects since Big-Oh is ...
1
vote
1answer
670 views

Is log(n) in complexity class P?

$\log(n)$ is not polynomial; is a problem solvable in $\mathcal{O}(\log n)$ time in P? $n\times \log(n)$ is also not polynomial; is a problem solvable in $\mathcal{O}(n\times \log n)$ time in P? If ...
3
votes
1answer
38 views

What does does $O$ mean in this context?

I understand big O notation in computational complexity theory, but I don't see how it applies in the equation below. From Pattern Recognition and Machine Learning: If we weren't familiar with ...
0
votes
0answers
13 views

Creating an algorithm with a certain worse case runtime [duplicate]

The inputs are x sorted lists (in increasing order) and in each list there are j/x elements (we are assured the numbers will work out to be a natural number. eg: j = 9, x = 3 L1 = [1, 2, 5], L2 = ...
0
votes
1answer
31 views

Big O notation comparison with constant time [duplicate]

So, I'm new to this whole asymptomatic notation with respect to algorithms. So say you have a $f(n) = 1/n$ and $g(n) = 1$, would it be OK to say that $f(n)$ is not equal or is not an element of ...
0
votes
0answers
16 views

What would be the expected number of clashes if I had a random hash function h to hash n distinct keys in an array T of size m. [duplicate]

I'm learning about hash functions and the way they work. Im not sure how I find the number of crashes. Collisions are solved with chaining and I think the results should be written in Big Oh and ...
2
votes
1answer
189 views

Prove transitivity of big-O notation

I'm doing a practice question (not graded HW) to understand mathematical proofs and their application to Big O proofs. So far, however, the very first problem in my text is stumping me wholly. ...
0
votes
1answer
27 views

Why is $f(n) = \Theta(g(n))$ where $f(n) = n(n+1)/2$ and $g(n) = \sum_{i=1}^n (n/i)^2$?

Why is $f(n) = \Theta(g(n))$ where $f(n) = n(n+1)/2$ and $g(n) = \sum_{i=1}^n (n/i)^2$? Also, why is $f(n) = \Theta(g(n))$ where $f(n) = n^{\log_49}$ and $g(n) = 3^{\log_2 n}$? I know what notations ...
0
votes
3answers
44 views

Complexity of BST [duplicate]

I have the following pseudo-code for printing all nodes of a BST : ...
2
votes
1answer
77 views

Why is the complexity of this nested for loop not $O(n^2)$?

I have the following pseudo-code: mystery(n): if n <= 50 : for i = 1 ... n : for j = 1 ... n : print i*j else : mystery(n-1) For ...
0
votes
1answer
34 views

Merge Sort proof [duplicate]

I am trying to prove that merge sort is indeed $O(n \log n)$. I was able to extract a pattern using constants, however now I am stuck. This is as far as I can get: $T(n) = 2T(n/2) + cn$ $T(n/2) = ...
-1
votes
1answer
57 views

Big Omega Counterexample?

I am doing homework to practice for my midterm exam and cannot answer this question. I need to decide whether or not this statement is true of false and either give a proof or counter example. For ...
4
votes
3answers
69 views

If $f$ and $g$ are increasing functions, are we guaranteed that $f=O(g)$ or $g=O(f)$? [duplicate]

Given two increasing functions $f$ and $g$ with values in the natural numbers, is it always the case that either $f\in O(g)$ or $g\in O(f)$. If the statement is true, then can anyone provide a ...
1
vote
2answers
47 views

Complexity of nested loops [duplicate]

I'm trying to figure out the complexity of the following algorithm. ...
0
votes
0answers
61 views

Why is removing the second largest element from a max-heap not in O(log n)?

I have a max PriorityQueue designed using a heap. A function removemax() that removes and returns the element with the largest priority in $\Theta(\log n)$ and a function insert in $\Theta(\log n)$ ...
0
votes
1answer
55 views

Solving a recurrence relation using Divide and Conquer Master Theorem [duplicate]

For the recurrence relation $$T(n) = 16T(n/4) + n!\,,$$ I have found that $T(n)\in Θ(n!)$. Can this be deduced using the Master Theorem?
0
votes
3answers
54 views

Can the runtime of functions with no loops change with the number of calls?

How can we perform time complexity analysis on a function that has no loops? int somefunction(int param) { if (something) do this; else do this; } ...
6
votes
3answers
570 views

Can a Minimum Possible Efficiency be proven?

Given a problem, is it possible to prove what the best worst-case efficiency of an algorithm to solve this problem would be? For example, lets take the problem of sorting an array. Many of the ...
0
votes
1answer
51 views

Which of $2^{\log_*n}$ and $\log\log n$ grows faster?

Function 1: $2^{\log_*n}$ Function 2: $\log(\log n)$ The first function is 2 to the log-star of $n$, the second function is log of log of $n$. What I need to know is which one is Big-Omega of the ...
1
vote
2answers
139 views

More efficient DFS on trees

Lets say for simplicity sakes I have a simple balanced binary tree of height h and I am doing Depth First Search. I generally do the following skeletons: ...