0
votes
1answer
20 views

Tight bound of worst case performance of algorithm

I am trying to find the "tight bound of an algorithm for the worst case run time. I have found that the upper bound of the worst case is O(n), I have also found that the lower bound for the worst case ...
0
votes
0answers
24 views

Why $17T(n/16) + n \log n$ satisfies the case 2 of the Master Theorem?

Using the Master Theorem, we have that $17T(n/16) + n \log n$ is $\theta(n^{log_{16}17} log^2 n)$ My question is, why $n \log n = \theta(n^{\log_{16}17} \log^1 n)$, being $\log_{16}17$ approximately ...
2
votes
1answer
57 views

From programming to mathematics

I'm studying algorithms design and analysis, but there is a code that I can't understand. I know that: Let $\mathcal P$ be the main program, and $\mathcal P \in O\left(\varphi(n)\right)$ with ...
0
votes
2answers
32 views

Sum of a sum [algorithm design and analysis]

I'm studying the algorithm analysis of one piece of code, and I have to find the big-O notation of the sum of a sum. ...
0
votes
0answers
25 views

Master Theorem Exercise

Could you please help me with a master theorem equation i have? for master theorem we have T(n) = aT(n/b)+f(n) where a>=1, b>1 here i have: T(n) = 5T(n/4)+12 a = 5; b = 4 and f(n) = 12; Now is c = 0 ...
0
votes
1answer
45 views

Calculating run times of programs with asymptotic notation

When calculating the run time of programs using asymptotic notation, I know how to set up the sums for things like for loops, but I'm getting stuck on summing them up. Sorry if this is a dumb ...
0
votes
1answer
26 views

Proving Upper Bound for Two Variable Function?

The question is: Prove (logn)^k = O(n) for every k>=1. I have never encounter a problem for proving an upper bound for two variables, so I am perplexed as to ...
0
votes
0answers
43 views

Why can I not generalize O(n^log5) for squaring matrice of size n

I have a question that is bugging me for around a 3 days, I first asked this question in stackoverflow but no one could answer it reasonably though they tried to help, so finally I found here as a ...
0
votes
1answer
48 views

Time efficiency of brute force algorithm as a function of number of bits?

This is homework help so advising how to solve such a problem is appreciated. The question reads as follows: What is the time efficiency of the brute-force algorithm for computing $a^n$ as a ...
0
votes
1answer
32 views

Derive Time from Sorting Method/Time Complexity

A sorting method with “Big-Oh” complexity O(n log n) spends exactly 1 millisecond to sort 1,000 data items. Assuming that time T(n) of sorting n items is directly proportional to n log n, that ...
2
votes
2answers
74 views

Prove that $\mathcal{O}(f_{1}(x)+ \dots +f_{n}(x))= \mathcal{O}(\max(f_{1}(x), \dots ,f_{n}(x)))$

I want to prove the following that based on maximum rule of functions: $$\mathcal{O}(f_{1}(x)+ \dots +f_{n}(x))= \mathcal{O}(\max(f_{1}(x), \dots ,f_{n}(x)))$$ the base prove is for each 2 functions ...
0
votes
3answers
124 views

Prove Upper Bound (Big O) for Fibonacci's Sequence?

NOTE: We are not to use proofs (limits, induction, or otherwise) in this problem. We were to prove the upper bound for the Fibonacci recursion is some exponential. The Fibonacci recurrence relation ...
1
vote
1answer
72 views

Help with Recursive Algorithm

We are to determine a recurrence relation for a recursive algorithm. Let us use the Josephus Problem for this: Given n people standing in a circle, every kth person is killed until one person ...
1
vote
1answer
36 views

Calculating algorithmic complexity

Given the following bit of code, how would I calculate the complexity? ...
1
vote
2answers
125 views

Derivative of $n^{\log n}$?

What would be the derivative of $n^{\log n}$? I have to prove that $(\log n)^n$ = $\omega$($n^{\log n}$). I am trying to implement L'Hopital rule.
3
votes
2answers
78 views

Why does taking logs of exponential functions affect growth rate?

We were doing a quick review of undergrad topics the other day in my grad Algorithms class and the professor asked a simple question: Which grows faster, $2^n$ or $3^n$? Everyone was quick to agree ...
0
votes
0answers
31 views

Potential values of minimum cost maximum flow algorithm

I have a simple directed graph $G(V,E)$ that has a source $s$ and sink $t$. Each edge $e$ of $G$ has positive integer capacity $c(e)$ and positive integer cost $a(e)$. I am trying to find the minimum ...
0
votes
2answers
56 views

Prove that so and so is $O(x^4)$

Given $f(x) = x^3 + 20x + 1$, how would I prove this is $O(x^4)$? By definition, the function is $O(x^4)$ iff $f(x) <= cn^4$, where $c$ is some constant. However, I'm not sure where to go from ...
1
vote
1answer
20 views

Correctness of complexity analysis of recursive algorithm

Given following recursive equation: $$T(n) = T(n-3) + \Theta(1)$$ Is it correct that this equation is O(1)?
0
votes
1answer
210 views

merge sort vs insertion sort time complexity

How do I solve exercise 1.2-2 from Introduction to Algorithms 3rd Edition, Author: Thomas H. Cormen Would I need to set both sides equal to each other and solve for n?
0
votes
1answer
50 views

Time complexity in terms of theta notation [duplicate]

sum= 0; for (i = n; i > o; i = i/3) for (j = 0; j < n^3; j++) sum++; what is the time complexity (in Θ- notation) in terms of n? so far, i've gotten to this point: The ...
-1
votes
1answer
92 views

Time complexity function in terms of theta notation

sum = 0; for (i = 0; i < n; i++) for (j = 1; j < n^3; j = 3*j) sum++; what is the time complexity (in $\Theta$-notation) in terms of ...
0
votes
1answer
56 views

Finding missing two edges in a MST in O(m) time

I need to write an algorithm in O(m) time to find the missing two edges of a minimum spanning tree. I am given a graph G(V,E) where m = |E| and n = |V| as an adjacency list, and T, a subset of G, with ...
1
vote
1answer
74 views

running time of a multiplication algorithm

Here is a multiplication algorithm: given inputs x and y, add x to itself y - 1 times: z = 0 while y > 0: z = z + x y = y - 1 return z What is the running time of this algorithm? Is it ...
0
votes
1answer
19 views

consider the following subroutine, what is the running time

Suppose A(.) is a subroutine that takes as input a number in binary, and takes time O($n^2$), where n is the length (in bits) of the number. (a) Consider the following piece of code, which starts ...
2
votes
3answers
103 views

how does the n-bit number related to big O notation

in algorithms you frequently have to evaluate problems like this, Let $x$ be an $n$-bit integer. For each of the following questions, give your answer as a function of $n$. my question is simple, ...
0
votes
2answers
64 views

Meaning of $O(n)$ in an expression

As my mathematical knowledge is increasing, I have been seeing more and more of $O(n)$ implementation in expressions. Here is what I mean. Example: $$z^{q_{N+1} + q_N} w^{q_{N+1} + q_N} (-1)^N (w-1)/w ...
0
votes
2answers
42 views

Algorithm analyse with Theta notation

Is $(n \log n) + \frac{\lfloor (\log n)^2\rfloor + \log n}{2} = \Theta(n \log n)$ ? My solution: $$ \begin{aligned} c_1 \cdot (n \log n) \le\,& (n \log n) + \frac{\lfloor(\log n)^2\rfloor + ...
0
votes
0answers
112 views

Solving recurrence using Master Theorem: Change of variables

Solve the recurrence using the Master Theorem State case and constant values used. $$T(n)=3T(\sqrt[3]{n})+log^2n$$ The $\sqrt n$ has a 3.(The number is a little small) I need to solve this using ...
0
votes
1answer
162 views

Prove that Big O (lg n) is a subset of Big O(sqrt(n))…

Prove that Big O (lg n) is a subset of Big O(sqrt(n)) and exists an element x in set Big O(sqrt(n)) that is not in Big O(lg n). This is a home work question and I have no clue where to start. Do I use ...
0
votes
3answers
78 views

Recurrence Master Theorem Question

Solve the recurrence $$T(n) = T({2n\over5}) +n$$ My attempt: $a=1$,$\ b=\frac 52$, $f(n)=n$ For the most part I believe that is correct. Now I was wondering if my math is correct in this next ...
1
vote
1answer
59 views

Prove that $\log_2 n$ is not bounded polynomially from below, need 2nd step

i.e. that $\log_2 n\not\in\Theta(n^x)$ for any $x > 0$ i shall not use induction on $x$ ( as $x = 1$ base case etc) my guess is : i use the def. of big theta: $$ 0≤c_1·n^x \le \log_2 n \le c_2· ...
3
votes
1answer
954 views

Big O estimate of simple while loop

Give a big-O estimate for the number of operations, where an operation is an addition or a multiplication, used in this segment of an algorithm (ignoring comparisons used to test the conditions in the ...
1
vote
1answer
68 views

Prove $T(n) = 2T(\frac{n}{2} - 3) + n$ is $O(n\lg n)$

I just had an exam in my algorithms class and this was a question on it. I was able to craft a solution, but I'm not sure if my proof has errors. $$\begin{align} &\frac{n}{2}-3 < n & ...
0
votes
0answers
72 views

In this insertion sort algorithm for example, how would I prove the algorithm's time complexity is O(n^2)?

Take the following insertion sort algorithm: I know it's O(n^2) fairly easy by examining it. But as far as proving it's O(n^2), how would I go about doing that? I could add up all the operations, ...
1
vote
1answer
97 views

Running time of a function of n with while loop

Provide a tight Θ bound on the running time of the function of n. ...
2
votes
2answers
55 views

Running time of a function of n

Provide a tight Θ bound on the running time of the function of n. for a=1 to n for b=1 to lg(n) for c = 1 to 23 x = 2x My thinking in solving ...
0
votes
2answers
388 views

Is 'every exponential grows faster than every polynomial?' always true?

My algorithm textbook has a theorem that says 'For every $r > 1$ and every $d > 0$, we have $n^d = O(r^n)$.' However, it does not provide proof. Of course I know exponential grows faster ...
0
votes
1answer
41 views

Comparing algorithm running times expressed in complex form

I know how to compare running times of different algorithms. Sometimes it is obvious, sometimes it requires simplifications, and sometimes dividing and using L'Hopital's rule to see if it converges ...
1
vote
1answer
50 views

Growth rates that follow : $f(n) \not\in Og(n)$ and $g(n) \not\in Of(n)$

Ok so the problem I am interested in is $f(n) \not\in Og(n)$ and $g(n) \not\in Of(n)$ dealing with natural numbers into positive reals, ($\mathbb{N}$ $\rightarrow$ $\mathbb{R+}$ ) O is a comparison ...
1
vote
1answer
48 views

Big-O Example question

Could you please give an example that disproves the following Big-O comparison: $$f(n)^2=O(g(n)^2)\qquad\text{implies}\qquad constant^f=O(constant^g)$$
0
votes
1answer
135 views

Prove or counterexample: $f(cn) \in \theta (f(n))$

Prove or provide a counterexample: For every positive constant c, and every function f from nonnegative ints into nonnegative reals, $$f(cn) \in \theta (f(n))$$. At first, I thought this was obvious, ...
3
votes
1answer
2k views

Upper bound for $T(n) = T(n - 1) + T(n/2) + n$ with recursion-tree

I'm reading through Introduction to Algorithms, 3rd ed. and I got stuck on the following recurrence (exercise 4.4-5): $$T(n) = T(n - 1) + T(n/2) + n$$ The exercise asks you to find the upper bound ...
3
votes
5answers
326 views

Provide an algorithm $O (n ^ 3 \log n)$, any example?

Provide an algorithm computing performance $O (n^3 \log n)$. Your algorithm should contain only simple operations. Any idea of how to approach this problem?...I am studying for the computer science ...
0
votes
2answers
38 views

Running time of adding $n$ items

I am trying to calculate how many binary additions it takes to add $n$ items. I see that with each iteration of binary addition, I am left with $n/2$ items so I see that it would take $\log_2 n$ ...
1
vote
2answers
363 views

Finding Big-O with Fractions

I'd want to know how I can find the lowest integer n such that f(x) is big-O($x^n$) for a) $f(x) = \frac {x^4 + x^2 + 1}{x^3 + 1}$ I've fooled around with this a bit and tried going from $\frac ...
0
votes
0answers
25 views

limit of cummulative binomial

How do you study limiting behaviour of cummulative binomial function $F(x;d,p)$ ? \begin{equation} F(x;d,p) = \sum_{r=0}^{x} \binom{d}{r} p^r (1-p)^r \end{equation} If $N$ is total number of nodes ...
1
vote
1answer
163 views

floors and ceilings in Master theorem

I am trying to go through the proof of the Master Theorem in Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, "Introduction to Algorithms (2nd or 3rd Ed.)" where it shows ...
1
vote
4answers
164 views

How is “n+n/2+n/4…1” equal to “2n-1” using the formula for geometric series?

I never knew not having good knowledge of basic maths will be so crippling!! So please help me out this time. I'll be working on my maths from today on. I was discussing about complexity of an ...
1
vote
1answer
67 views

Why is it okay to do this?

I am studying asymptotic recurrences for algorithms, and the book says: $$T(n) = 2T(n/2) + \Theta (n)$$ is technically $$T(n) = T(\lfloor n/2 \rfloor) + T(\lceil n/2 \rceil) + \Theta (n)$$ for an ...