Questions about asymptotic notations and analysis

learn more… | top users | synonyms (2)

1
vote
2answers
40 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.
10
votes
9answers
2k 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
41 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
59 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
112 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, ...
4
votes
1answer
53 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
47 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
50 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
23 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
29 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
283 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
102 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
62 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
30 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
34 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 ...
0
votes
2answers
58 views

How can random array access be considered $O(1)$ if bits must be stored in space and light travels at finite speed?

Bits are usually stored linearly in space. We can say, thus, that the length of a memory chip, for example, is linearly proportional to the number of bits it can hold. Since signals must travel at ...
0
votes
1answer
24 views

Prove the upper bound on $T\left(n\right)=T\left(\log_{2}n\right)+O\left(\sqrt{n}\right)$ [duplicate]

I need some help with the following recursion: $T\left(n\right)=T\left(\log_{2}n\right)+O\left(\sqrt{n}\right)$ More specifically I wish to find and prove the upper bound on it. I have a hunch it ...
1
vote
1answer
27 views

Big-O Notation for Menezes-Vanstone Elliptic Curve Cryptography?

I need someone help me about . how can compute time complexity for this algorithm (Menezes-Vanstone Elliptic Curve Cryptography). I have spent much time reading journals and papers but as yet have ...
3
votes
1answer
48 views

Explanation of Summations for Algorithm Analysis

I do not have a background in Computer Science, work as a Software Engineer, and am attending college for my Master's degree in Computer Science. I have a data structures and algorithms course that I ...
0
votes
1answer
41 views

Big O Notation Explained [duplicate]

Our teacher gave us the following definition of Big O notation: O(f(n)): A function g(n) is in O(f(n)) (“big O of f(n)”) if there exist constants c > 0 and N such that |g(n)| ≤ c |f(n)| for all n > ...
3
votes
2answers
38 views

Time Complexity $\Theta$ vs. $\Omega$ [duplicate]

If an algorithm has running time of $\Theta(n^2)$, is it possible to have a best-case running time of $\Omega(n)$? Or is the fastest running time only $c n^2$ for some constant factor $c$?
0
votes
1answer
24 views

Comparing $2^{F_n}$ and $2^{\varphi^n}$

if we define $F_n$ be the $n$th fibonacci number and $\varphi$ be golden number then can we say that $2^{F_n} \in \Theta(2^{\varphi^n})$ or in other word $2^{\frac{\varphi^n - ...
6
votes
1answer
739 views

What is the Big O of T(n)?

I have a homework that I should find the formula and the order of $T(n)$ given by $$T(1) = 1 \qquad\qquad T(n) = \frac{T(n-1)}{T(n-1) + 1}\,. $$ I've established that $T(n) = \frac{1}{n}$ but now ...
0
votes
1answer
45 views

Master Theorem Questions?

NOTE: I asked this on mathstackexchange, but didn't get the responses I wanted, thought I should post in CS. Sorry if i did something wrong but i am a newbie. State the asymptotic (worstcase) ...
3
votes
1answer
40 views

Offline scheduling fully determined arbitrary jobs in multiprocessor setting

Let $\mathcal{J} = \{J_1,...,J_n\}$ be a set of jobs with each $J_i = [a_i,r_i,d_i]$ where the job becomes available at its arrival time $a_i$, requires $r_i$ execution time and needs to be finished ...
1
vote
3answers
33 views

How to find $c$ and $n_0$ for Big-Oh questions

I understand the theory behind the definition of Big-Oh, but when I try a question, I don't get how you would find the $c$ and $n_0$ values. For example: if $f(n) = n!$ and $g(n) = 2^n$, how would I ...
-1
votes
1answer
89 views

Runtime of nested loops

What is the asymptotic runtime of fthe ollowing piece of code in terms of number of updates to S in worst case. ...
6
votes
2answers
169 views

Is $n$ times $O(1)$ equivalent to $O(n)$? [duplicate]

I am having a hard time figuring out if $$\sum^n_{i=0} O(1) =O(n)\,.$$ I think it doesn't but I am unable to find a convincing explanation for that, does anyone have an intuitive yet mathematical ...
6
votes
1answer
64 views

Use of Big O Notation in a recent paper by Khot et al

I'm reading a paper about Constraint Satisfaction Problems, specifically "A Characterization of Strong Approximation Resistance", Subhash Khot, Madhur Tulsiani, Pratik Worah (ECCC TR13-075). The ...
1
vote
2answers
79 views

Finding recursion for runtime of code [duplicate]

This is the first time we have to do recursive/closed form expressions WITH code in class and I really have no idea how to approach this. My course notes that the prof put up don't really help as he ...
0
votes
0answers
17 views

Show that n^2 is Big Omega(n lg n) [duplicate]

Also, is n O(n lg n)? I'm trying to understand this notation to better understand Big O. (Apparently they ask you questions about Big O in interviews, so I wanted to learn). I found a few formulas ...
2
votes
1answer
51 views

Show that 6n^2 + 12n is O(n^2) [duplicate]

I understand how I would do this if the problem were as such $8n + 5$ is $O(n)$ $c>0$ and an integer constant $n(not 0) \geq 1$ such that $8n + 5 \leq cn$ for every integer $n \geq n(not 0)$ we ...
0
votes
0answers
13 views

Least upper bounds on complexities [duplicate]

In popular literature, complexities are usually used in a very imprecise manner, often to describe the runtime performance of an algorithm and denoted with "$O$". My question is about these Landau ...
0
votes
2answers
67 views

Prove, using only the definition of $O()$, that $2^{\sqrt{x}}$ is not $O(x^{10})$ [duplicate]

Prove, using only the definition of $O()$, that $2^{\sqrt{x}}$ is not $O(x^{10})$. I have been doing a few exercises on Big O and this is the first time I have encountered the variable in the ...
2
votes
3answers
60 views

Are there functions in the same Θ-class that are not linear transformations of each other?

looking for some help, or at least if I'm going the right direction... Are there functions $f$ and $g$ such that $f$ is $O(g)$ and $g$ is $O(f)$ and NO constants $c_1$ and $c_2$ exist for which ...
1
vote
2answers
43 views

Asymptotic Proofs - BigOh/BigTheta

This is not homework, but from a past exam. I do not know how to solve this one at all. Can anyone please take the time and show me how to do these? Thank you. Prove that $5^n \in O(6^n)$, but ...
0
votes
1answer
102 views

What is the runtime of the following code? [duplicate]

Can you explain to me how you get the Big O notation for the runtime of the following snippet of code? ...
1
vote
1answer
55 views

Intuition behind recurrences with growth O(n log n) vs O(n²)

Been trying to get the intuition behind why two very similar recurrence relations don't follow a pattern I would expect. They are pretty well known relations: Relation 1 - $T(n) = 2T(\frac{n}{2}) + ...
0
votes
2answers
70 views

How to show whether $n2^n = 2^{O(n)}$?

show whether $n2^n = 2^{O(n)}$ is true or not. In my opinion, it's false because O(n) can be n and thus the equality will be wrong, because $n2^n$ grows much faster than $2^n$
2
votes
1answer
63 views

Why do Θ-bounds not survive taking differences?

$f_1$, $f_2$, $g_1$, and $g_2$ are functions such that: $$f_1 = \Theta(f_2)$$ $$g_1 = \Theta(g_2)$$ I was able to prove that: $$\frac{f_1}{g_1} = \Theta\biggl(\frac{f_2}{g_2}\biggr)$$ But I can't ...
0
votes
1answer
29 views

Comparing Big O Complexity [duplicate]

I'm trying to compare two functions, such as f(n)=n^n and g(n)=n^10^10. I'm unsure if f(n) is O(g(n)) or vise-vera where g(n) is O(f(n)). From my understanding, n^n can be worse than n! and although ...
0
votes
0answers
30 views

Not sure if my recurrence is correct for T(n) = 2T(n^.5) + O(1) [duplicate]

I have T(n) = 2T(n^.5) + O(1) = 2(2T(n^.25) + O(1)) + O(1) = 2(2(2T(n^.125) + O(1)) + O(1)) + O(1) and so on To me this seems wrong, and I ...
2
votes
1answer
97 views

Can a Big-Oh time complexity contain more than one variable?

Let us say for instance I am doing string processing that requires some analysis of two strings. I have no given information about what their lengths might end up being, so they come from two distinct ...
0
votes
2answers
77 views

How to simplify the sum over 1/i?

With the recurrence relation: $$ T(n) = 2T\left(\frac{n}{2}\right) + \frac{n}{\log(n)}$$ The "sum for all levels" in the recurrence tree is: $$ \sum_{i=0}^{\log n -1} \frac{n}{\log n - i} = ...
-1
votes
1answer
22 views

Question Concerning Big-O Notation

A couple of questions: When choosing $C$ do I have to choose an integer? I see nothing in my definitions preventing fractions, but I haven't seen any in anything I've looked up, either Given ...
3
votes
2answers
61 views

Origins of misconception about using equality signs with Landau notation

From "Misconception 1" from Søren S. Pedersen's blog, and as many have seen before, a major misconception in Big-O (and others) notation is to say a function is "equal" to Big-O of some other ...
0
votes
1answer
65 views

Showing that tournament sort requrires O(n log n) comparisons

I wish I could think of a better way to word my question. Maybe some one here could offer s suggestion for that, as well. On to my question. Before I do, this is a class question that has been asked, ...