Questions about asymptotic notations and analysis

learn more… | top users | synonyms (2)

1
vote
1answer
22 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 ...
1
vote
1answer
45 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
20 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
24 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
279 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
92 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
58 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
29 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
31 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
25 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
53 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
23 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
20 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
45 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
31 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
35 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
737 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
43 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
38 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
32 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
84 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
165 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
62 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
50 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
11 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
56 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
50 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
69 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
62 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
29 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
92 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
73 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
19 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
53 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, ...
0
votes
0answers
29 views

Asymptotic Complexity of the following two functions [duplicate]

Let $f(n) = n^{1.01}$ $g(n) = n(log(n))^2$ Now I need to figure out whether $f = O(g(n))$ or $\Theta(g(n))$ or $\Omega(g(n))$. I tried taking the ratio $f(n)/g(n)$, apply L'Hospital's rule ...
4
votes
2answers
41 views

What is my error in reasoning about the complexity class $n^{o(1)}$

I'm almost sure I understand $o(1)$ (a class of functions that converge to zero in their limit), but the way I understand it, that would seem to imply that functions in $n^{o(1)}$ converge to 1 (after ...
0
votes
1answer
27 views

How do I prove all constants to some exponential power belong to little-o of some function [duplicate]

I'm trying to prove that c2n = o((loglog n)n) (That's little-o) for any constant c. I understand that we can prove one function grows at a smaller rate than the other by taking the limit as n ...
2
votes
1answer
64 views

Which article in front of O(.), Ω(.), …?

Writing a survey, I am confronted to a very difficult and -- I dare say -- deep issue: I have many sentences mentioning or stating results of the form "a $\Omega(\sqrt{n})$ lower bound", or "a ...
0
votes
0answers
30 views

Proof of Asymptotic Fact [duplicate]

I was trying to prove the next exercise 1 It's not look so hard, but with some tries, I couldn't find out a way to show it, I was supposed wrong assumptions. To convince myself if that relation ...
3
votes
3answers
363 views

What is the notation for bounding running time in worst case with concrete example resulting in that worst case running time

I know that Big O is used to bound worst case running time. So an algorithm with running time $O(n^5)$ means its running time in worse case is less than $n^5$ asymptotically. Similarly, one can say ...
0
votes
2answers
61 views

Can we construct a binary tree with width and height Θ(n)?

we know this definition: Given a binary tree, Width of a tree is maximum of widths of all levels. Let us consider the below example tree. ...