Questions about asymptotic notations and analysis

learn more… | top users | synonyms (2)

2
votes
1answer
20 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
32 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
84 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 ...
-2
votes
0answers
29 views

what is the upper bound of log(log(log(n)))? [duplicate]

Suppose we take log(log(log (n))) = O (n ^ 1/3) . It is true but how to prove it mathematically? Is there any general way to calculate upper and lower bounds for these types of functions ?
-1
votes
0answers
16 views

Using Limsup at asymptotic comparison between two functions

Ok, so let $f(n) = (1 + (-1)^n)n^3 + 2$ and $g(n) = 2n^2$ I have to find the right of these options: a) $f \in \Theta(g)$ b) none of the other options c) $f \in o(g)$ d) $f \in \omega(g)$ Since ...
3
votes
1answer
42 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
35 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
24 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
28 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
40 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
91 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
39 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
665 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
25 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
134 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
41 views

Complexity of BST [duplicate]

I have the following pseudo-code for printing all nodes of a BST : ...
3
votes
1answer
70 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
66 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
46 views

Complexity of nested loops [duplicate]

I'm trying to figure out the complexity of the following algorithm. ...
0
votes
0answers
57 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
54 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
52 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
566 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
39 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
135 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: ...
1
vote
1answer
41 views

Big Omega of 3-Sum Algorithm [duplicate]

An optimized algorithm for the 3-sum problem with an input array N has O(N^2logN) however I read that the Big Omega for this ...
0
votes
1answer
59 views

Which complexity class $3^{n/3}$

Assuming a problem has complexity $O(3^{n/3})$, Which is its class of complexity ? Despite that it is not as $2^{n}$ ,we can say is an exponential ?
3
votes
2answers
64 views

If $T(n+1)=T(n)+\lfloor \sqrt{n+1} \rfloor$ $\forall n\geq 1$, what is $T(m^2)$?

$T(n+1)=T(n)+\lfloor \sqrt{n+1} \rfloor$ $\forall n\geq 1$ $T(1)=1$ The value of $T(m^2)$ for m ≥ 1 is? Clearly you cannot apply master theorem because it is not of the form ...
1
vote
1answer
45 views

What is the correct representation of Master Theorem?

What I'm taught in my class - $T(n)=aT(\frac{n}{b})+\theta(n^k\log^pn)$ where $a\geq1$, $b>1$, $k\geq1$ and $p$ is a real number. if $a>b^k$ then, $T(n)=\theta(n^{\log_ab})$ if ...
-3
votes
1answer
74 views

Complexity Analysis for a nested loop with two methods [duplicate]

Hey I am studying for my intro algorithms class final and I'm not sure if I'm understanding this question correctly (its from a sample final exam). If someone could explain this to me that would be ...
1
vote
2answers
78 views

If algorithm runs $\theta(n)$ in time T, doubling input size has what effect on time T?

In other words, is there a relationship between the step size and the actual running time? Suppose that the algorithm is run on identical machine.
19
votes
11answers
5k views

“For small values of n, O(n) can be treated as if it's O(1)”

I've heard several times that for sufficiently small values of n, O(n) can be thought about/treated as if it's O(1). Example: The motivation for doing so is based on the incorrect idea that O(1) ...
0
votes
2answers
42 views

In general, does $f(g)$ and $f(h)$ have the same time complexity?

I thought about this question while looking at a textbook where it wanted me to compare the time complexity of $\lg^*(n)$ and $\lg^*(\lg(n))$ Now it is well known that $\lg^*$ is a tremendously slow ...
0
votes
1answer
64 views

Big O Asymptotic complexity [duplicate]

I am trying to rank $\log n $, $\log_{10} n $, $n \log n $, $n \log n^2 $, $n^{0.8}$, $\sqrt{n}$ in increasing asymptotic complexity. $\log n $ has base 2 unless specified otherwise. The answer I ...
2
votes
3answers
117 views

Papadimitrou and standard landau notation

This is a homework. I'd appreciate if you didn't give away answer straightaway but instead pointed me to the right direction. From huge majority of sources the definition of $\mathcal{O}(n)$ is: $f, ...
6
votes
1answer
75 views

Solving recurrence relation $T(2n) \leq T(n) + T(n^a)$

I want to prove that the time complexity of an algorithm is polylogarithmic in the scale of input. The recurrence relation of this algorithm is $T(2n) \leq T(n) + T(n^a)$, where $a\in(0,1)$. It ...
2
votes
1answer
60 views

Is this time complexity quasi-polynomial?

I have been working in the time analysis for an algorithm and finally I got a curve that fits: $O(2^{(\log_2(N)^{2.01})})$ N is the number of elements. I'm right to say the above time complexity is ...
1
vote
1answer
24 views

Implement opposite() method to tell if there are two opposite numbers, (x,-x)

Let a dictionary with the operations insert(), delete() and search(). Each one of them ...
2
votes
1answer
56 views

Why is $O(\log_{M/B} N/M)$ the same as $O(\log_{M/B} N/B)$?

Where $N$ is the size of the input, $M$ is the size of your main memory and $B$ the amount of elements that you can transfer in one I/O. My idea is that since $B$ is usually much smaller than $M$ we ...
2
votes
1answer
28 views

Expressing pseudo-polynomial runtime solely in terms of the input size

In case we have an algorithm which is pseudo-polynomial and runs in $O(n^2C)$ for some $C$ that is encoded in binary. Is it correct to say that if $C=2^n$ then $O(n^2C)=O(n^22^n)$ and because ...
0
votes
1answer
36 views

Solve a recurrence relation with two recursion calls using the iteration method [duplicate]

I can't figure out how to solve this recurrence relation using the iteration method: $$T(n) = \begin{cases} 0, & \text{if $n=0$} \\ 1, & \text{if $n=1$} \\ 3T(n-1)+ 4T(n-2), & \text{if ...
4
votes
1answer
289 views

Can subtracting o(1) from the parameter of a function change its Θ-class?

I would like to know if it is possible that two functions $f(n), g(n)$ can exist such that both of the following conditions are met: $g(n) = o(1)$ $f(n-g(n)) \neq \Theta (f(n))$ I though I found ...
2
votes
0answers
31 views

Prove/Disprove that $f(n) + g(n)= O(g(n)*f(n))$? [duplicate]

I would like to know if this statement is true: I thought of giving a counter example by defining: which will give us that but i'm nut sure if it's possible to say that beacuse I suspect that it ...
2
votes
4answers
114 views

Does $f(n) + g(n) = O(g(n) \cdot f(n))$ hold?

I would like to know if this statement is true: $f(n) + g(n) = O(g(n)\cdot f(n))$. I thought of giving a counter example by defining: $f(n) = 3n^2$ ; $g(n) = n$ which will give us that $O(3n^3) = ...