Questions about asymptotic notations and analysis

learn more… | top users | synonyms (2)

0
votes
1answer
19 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
18 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
39 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
74 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
votes
0answers
17 views

How to solve equations that have asymptotic notations in equations?

Hi i'm new to algorithms and need some help understanding asymptotic notations. So my main issue is how do you go about solving equation to find whether they are true or not, such as n^2 + O(f(n) = ...
-1
votes
0answers
20 views

Proving asymptotic statements [duplicate]

How do you know whether each of the statement is true or false? $$Ω(n^3) + o(n^2) = Ω(n^3)$$ $$n + ω(\log n) = Θ(n)$$ I believe both of them are true because for each of them, no matter how the ...
1
vote
1answer
38 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
653 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
37 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 = ...
-1
votes
0answers
34 views

Show that n = o(n^log n) [duplicate]

I'm struggling to find an approach to answering this homework question. Show that: $$n = o(n^{\log n})$$ I intuitively understand that $n$ is linear and on sufficiently large input $n^{\log n}$ ...
0
votes
1answer
24 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
97 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
40 views

Complexity of BST [duplicate]

I have the following pseudo-code for printing all nodes of a BST : ...
3
votes
1answer
69 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
32 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
55 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
57 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
52 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
52 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
51 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
565 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
36 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
34 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
63 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
43 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
58 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
66 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
63 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
59 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
52 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
34 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
113 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) = ...
0
votes
2answers
70 views

Theta estimation of two functions

I'm in a data structures class, and am working on an assignment right now that asks me to find the theta complexity of certain loops. I missed class the day we were introduced to the topic, and ...
0
votes
1answer
32 views

Given $T(n) = \sum_{i = 0}^{\log n} i 2^i$, what is $O(T(n))$?

I'm trying to perform an asymptotic analysis on a function: $T(n) = \sum_{i = 0}^{\log n} i 2^i$ The above expression came about when I began with: $T(n) = \sum_{i = 0}^{\log n} 2^i \log (2^i)$ Is ...
1
vote
2answers
35 views

Show that functions in O(1) can't grow faster than their composition with themselves

Let $f(n)$ be a function s.t $f(n)\geq 1 $ for every $n$. I want to disprove that if $f(n) = \omega (f(f(n)))$ then it means that $f(n) = O(1)$. I thougt of 2 approaches to show that this ...
0
votes
2answers
28 views

Are there any exponential-time iterative algorithms?

Is it possible to implement an exponential-time algorithm using iteration, as opposed to recursion? I didn't have any particular algorithm in mind, I was just thinking theoretically. The way I was ...