Questions tagged [asymptotics]

Questions about asymptotic notations and analysis

Filter by
Sorted by
Tagged with
-1
votes
1answer
563 views

Solving a recurrence with the Master Theorem

Problem taken from here (page 3): http://cse.unl.edu/~choueiry/S06-235/files/MasterTheorem-Handout.pdf $T(n) = 3T(\frac{n}{2}) + \frac{3}{4}n + 1$ $f(n) = \frac{3}{4}n + 1$ It says we cannot use ...
-1
votes
1answer
29 views

Is $\sum_{i=1}^n i \in \Theta(n^2)$?

Please help me understand on how to prove or disprove the following. I have been practicing and doing others which are ok, but with this sum, it is rather confusing. $$\sum_{i=1}^n i \in \Theta(n^2)...
-1
votes
1answer
112 views

Prove Θ(n) + O(n^2) ≠ Θ(n^2)

How would I go about proving this statement? Θ(n) + O(n^2) ≠ Θ(n^2) I know how to prove if given a function f(n) if it's big o but I do not understand how to go ...
-1
votes
1answer
119 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 ...
-1
votes
1answer
191 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 ...
-1
votes
1answer
62 views

Is my analysis of this recurrence relation correct?

The following recurrence relation, $$T(n)=16T(\frac{n}{4}) + n^2$$ has been given to me to be solved via the Master Theorem. I'm pretty sure this is a case 2 situation, since $$\log_4{16} = 2$$ and ...
-1
votes
1answer
48 views

Solve recurrence with Master Theorem - Polynomially Smaller/Larger

The problem is to solve the recurrence using Master Theorem : $$T(n) = 2T(n/2)+\log_2 {n}$$ My attempt: $$ a=2, b=2, f(n)= \log_2 {n}, g(n)=n^{\log_b{a}}=n $$ I am torn between case 1 & the ...
-1
votes
1answer
47 views

confused with Time Complexity [duplicate]

I was reading book related to Time Complexity, and came up with 4 lines of equations that I could not understand properly, could you please explain why are those true? 1) $n = o(n\log\log n)$ 2) $...
-1
votes
1answer
66 views

Prove $ 8^n = Θ(4^n)$

how would I prove $ 8^n = Θ(4^n)$ is either true or false. I so far have attempted to prove big O but cant find the value of C1
-1
votes
1answer
104 views

Analyzing asymptotic notation $\sqrt n = O(\log^2 n)$

I am trying to determine whether $f(n) = \sqrt n$ is in $O(g(n))$, $\Omega(g(n))$, or $\Theta(g(n))$ where $g(n) = \log^2 n$. The answer says that only $f(n) = \Omega(g(n))$ is correct, but why isn't ...
-1
votes
1answer
73 views

Algorithms - In which relation to the big O notation are the functions lg n and ln n? [duplicate]

I want to prove in which relation the two functions stand to each other with the help of a proof. But how?
-1
votes
1answer
154 views

Proving that $\max(f(n),g(n)) = \Theta(f(n)+g(n))$

Prove that for every two positive functions $f(n),g(n)$: $$ \max(f(n),g(n)) = \Theta(f(n)+g(n)). $$ I've just started data structures and I barely understand it, so please be gentle with me.
-1
votes
1answer
69 views

Finding f(n) so 2T(f(n)) + 1 ∈ Θ(log^4 n)

Given the recursive function: ($c$ is a constant) $\qquad T(n) = \begin{cases}1 & n ≤ c\\2T(f(n)) + 1 & n > c\end{cases}$ I need to find a $f(n)$ such $T(n) ∈ Θ(log^4 n) = Θ(\log \log \...
-1
votes
2answers
281 views

Solve using master method $T(n) = n · T(n/2) + n^{\log n}$ [closed]

$T(n)=n\displaystyle \cdot T\left(\frac{n}{2}\right)+n^{\log_{2}n}$. $f(n) = n^{\log_{2}n}$ Number of leaves = $n^{\log_{a}b} = n^{\log_{2}n}$ CASE 2 (All level same) $f(n) = \Theta(n^{\log_{b}a} {...
-1
votes
1answer
59 views

Find and prove asymptotic upperbound for T(n) [duplicate]

How would I go about solving this?
-1
votes
1answer
1k views

Converting pseudo code to a recurrence relation equation? [duplicate]

The following is pseudo code and I need to turn it into a a recurrence relation that would possibly have either an arithmetic, geometric or harmonic series. Pseudo code is below. I have so far T(n) ...
-1
votes
2answers
412 views

How do I analyze Mergesort that uses Insertion Sort for small inputs?

I know that Insertion Sort is faster when size $N$ is a small number, hence by modifying Merge Sort to use Insertion Sort when size $N$ reaches $K$, can help improve the performance. How do I ...
-1
votes
1answer
98 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 ...
-1
votes
1answer
59 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 $f(x)=O(...
-1
votes
2answers
70 views

What is the Big-O runtime of this algorithm? [duplicate]

Can anyone explain why the runtime of this is in O(N^3)? Additionally, what would the run-time be in Big-OH if the else statement was removed. ...
-1
votes
1answer
70 views

What will be the computational complexity of a system with two pipelined algorithms?

A system consists of two separate algorithms (operated in pipeline). Algorithm#1 is iterated m times and has a time complexity ...
-1
votes
1answer
69 views

Big o notation help? [duplicate]

I'm learning about data structures and have been reading up on upper bounds. Most of the stuff I understand but my professor gave us a problem in class to solve on our own for fun. I'm not sure how to ...
-1
votes
1answer
41 views

Why $\left\lceil lgn \right\rceil <lgn+1\le 2lgn\quad for\quad all\quad n\ge 2$

I have some confusion about 3.2-4 in CLRS. Here is the question : Is the function $\left\lceil \log { n } \right\rceil !$ polynomially bounded? Is the function $\left\lceil \log { \log { n } } \...
-1
votes
1answer
218 views

Big O Running Time Analysis

What is the big O running time for following method() by counting the approximate number operation it performs. How can I identify the running time of each line? I ...
-1
votes
1answer
2k 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. ...
-1
votes
1answer
159 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) ...
-2
votes
1answer
4k views

Does ln n ∈ Θ(log2 n)? [duplicate]

Is that statement false or true? I believe it's false because ln(n) = log base e of n. So therefore, log base 2 of n can be a minimum because in 2^x = n, x will always be less than y in e^y = n. ...
-2
votes
2answers
163 views

How to solve equations using big Θ [duplicate]

How would I prove that the statement $10n^3+3n=Θ(n^3)$ is true/false?
-2
votes
1answer
2k views

What is the Big O of $2^{\log \log n}$? [duplicate]

What is the Big O class of the following expression: $$2^{\log \log n}$$ I think the Big O is $2^n$ as I assume $\log \log n$ to be $n$. Is my assumption correct?
-2
votes
2answers
497 views

How to do Big 'O' notations [duplicate]

How can I solve $\mathcal{O}$-notations without using Java or any other programming language? I only want to use pen and paper.
-2
votes
2answers
426 views

Understanding constants in big-O notation

I am having a difficult time understanding big-O notation for the growth of functions. My textbook says the following. Example 2 shows that $7x^2$ is $O(x^3)$. Is it also true that $x^3$ is $O(7x^...
-2
votes
3answers
2k views

Big O relationship between $n^{10\log n}$ and $(\log n)^n$ [duplicate]

I need help with a home task with computer science. the problem is: compare the two complexity functions: $F(n) = n^{10\log n}$ and $G(n) = (\log n)^n$. Which is $O(\ )$ of the other? Which is $\Omega(...
-2
votes
1answer
760 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 ...
-2
votes
2answers
70 views

prove that log((n^2)!)= o(log((n!)^2))

i have a question - how i can prove that: $\log((n^2)!) =\theta (log((n!)^2))$ i try something like that: $\log((n^2)!) = 2*(log(n)!)=\theta(2*(log(n)!)=\theta(n\ log(n)) $ $\ \theta(log(n!)^2)=\...
-2
votes
1answer
64 views

What is $\sum_{k=1}^\infty \frac{1}{k^2 H_k}$?

According to this answer, $\sum_{k=1}^\infty \frac{1}{k^2 H_k}$ is approximately 1.33275. How?
-2
votes
1answer
31 views

How can time complexities be elements of others? [duplicate]

I have a problem that I solved, but I'm unsure if my answers are correct or not. I've never seen the implementation of time complexities as elements of others. ...
-2
votes
1answer
73 views

Big O Notation - Find a Function That Represents the Statement

There's an f(n) such that f(n) != O(f(n/2)) so by the definition of big O notation: for ...
-2
votes
1answer
6k views

Complexity of a while loop that divides by parameter by three each iteration

I've learned that a while loop such as int i = 100; while (i >= 1){ ... ///Stuff i = i/2 } will run in logarithmic time, specifically, ...
-2
votes
1answer
40 views

What is the time complexity of the following triple nested loop? Kindly solve in term of n

I want to ask that what is the time complexity of this function (triple nested loop) .Kindly analysis completely so that I can understand. ...
-2
votes
2answers
91 views

Show that: $0.01n \log n - 2000n+6 = O(n \log n)$

Show that $0.01n \log n - 2000n+6 = O(n \log n)$. Starting from the definition: $O(g(n))=\{f:\mathbb{N}^* \to \mathbb{R}^*_{+} | \exists c \in \mathbb{R}^*_{+}, n_0\in\mathbb{N}^* s. t. f(n) \leq cg(...
-2
votes
1answer
30 views

Help with Big-O homework [duplicate]

"er" is the Danish equivalent of "is" in English. I need some help with the square root one. Additionally, it would be nice to know if the other ones are correct.
-2
votes
1answer
57 views

Solving double recurrence relation

How to calculate the rate of growth of the below function $f(x)$? $$ \begin{align*} f(x) &= \begin{cases} f(x-1) + g(x) & \text{if } x > 1, \\ 1 & \text{if } x \leq 1. \end{cases} \\ g(...
-2
votes
1answer
98 views

Intersection of functions given asymptotic relationship

If $f(n) = O(g(n))$ and $g(n) \neq O(f(n))$ than can we say that $f(n)$ and $g(n)$ will never intersect?
-2
votes
1answer
213 views

Complexity for minimum subset sum of size n-k

Disclaimer: Not a HW. Given $n$ sorted positive floating point numbers, and one has to find the minimum subset sum of size $n-k$. What would be the most efficient way? I can figure out using Brute ...
-2
votes
0answers
510 views

Want to understand Big O by graph [duplicate]

f(n) = 3n+3 ; f(n) = O(n) By definition : $3n+3 \le c_1.n$ By dividing both side by n $3+(3/n) \le c_1$ means we ...
-3
votes
3answers
169 views

Building a Hyper Computer

I had an idea for a theoretical super computer. Supposing, one was able to optimise(or significantly increase efficiency) all algorithms used in most computing tasks(An open source project on ...
-3
votes
2answers
838 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
142 views

Using Big $O,\Omega,\Theta$, how would you represent these equations?

How would you write the following equations in $O,\Omega,\Theta$ notation? $$ \begin{align*} t(n) &= 4n^4 + 3n^5 + 3n^6 \\ g(n) &= 2n^6 + 5\log n \\ f(n) &= 50n^5 \end{align*} $$
-4
votes
1answer
553 views

Equivalent definitions of big O

Let $A = \{ g(n) \mid \exists c,n_0 \, \forall n \ge n_0\colon g(n) \le cf(n) \}$, and $B = \{ g(n) \mid \exists c,n_0 \, \forall n \geq n_0 \colon g(n) < cf(n) \}$. Prove $A = B$. My ...
-4
votes
1answer
140 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!

1
18 19 20 21
22