Questions about asymptotic notations and analysis

learn more… | top users | synonyms (2)

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
28 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 ...
-1
votes
0answers
44 views

Is runtime Θ(n log n) ⊂ Θ(n² * log n)? [duplicate]

Is $\Theta(n \log n) \subset \Theta(n^2\log n)$? (Is $n \log n \in \Theta(n²\log n)$?) Thanks for your time, regards
3
votes
1answer
23 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
0answers
19 views

How to formally show that $f(n) = o(g(n))$ [duplicate]

Given $f(n)=n^{100}$ and $g(n)=2^{\frac{n}{100}}$, I can tell that $f(n)=o(g(n))$ mainly because $n^c=o(2^n), \forall c$. But how can I formally show that $f(n)=o(g(n))$. My attempt at this question ...
2
votes
1answer
166 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
52 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!
0
votes
1answer
26 views

how f(n) is O(g(n)) for the graph?

There is a lot of Explanation about big-0, But i'm really confused on this part. Acoording to the definition of Big-O in this function ...
2
votes
1answer
26 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
41 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
49 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
31 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
63 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
27 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
22 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
55 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
739 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
45 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
38 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
37 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
52 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
89 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
50 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
40 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
26 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
42 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
44 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
2answers
121 views

Example of worst case input for Build-Max-Heap

What would be an example of a worst-case input for Build-Max-Heap? What would the "shape" of it "look like"? I'm having trouble getting a feeling for it.
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
674 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
33 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
244 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
80 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 ...