0
votes
0answers
92 views

Please give me an example of the algorithm where $\Theta$ will be equal to $e^n$

Please give me an example of the algorithm where $\Theta$ or $O$ will be equal exactly to $e^n$ . The algorithm should not be simple counting from 0 till $e^n$ . It should be a clear relation of two ...
1
vote
2answers
42 views

How to find the asymptotic behavior of these sums?

Let $$X(n) = \displaystyle\sum_{k=1}^{n}\dfrac{1}{k}.$$ $$Y(n) = \displaystyle\sum_{k=1}^{n}k^{1/k}.$$ $$Z(n) = \displaystyle\sum_{k=1}^{n}k^{k}.$$ For the first, I don't have a formal proof but I ...
0
votes
0answers
46 views

Biggest common sub-string search asymptotics

What is the function of Big-O in case where we use brute-force on two strings to find the biggest common sub-string. Please can you explain the underlying logic to the resulting formula corresponding ...
0
votes
0answers
27 views

Theoretical question of physical analogies to different O(f(x)) based characteristics of algoritms

I want to better understand the following concepts: "n!", "e^n". I.e. what is the physical analogy of the functions at the bottom of the message. F.ex. for the "n^a" and "log a x" where a equals to ...
0
votes
1answer
26 views

Change of variables in function $T(n)$.

I've been given this recurrence to solve: $T(n) = T(\sqrt n) + \theta(lglgn)$ And I'm told that the way to solve it is to let $m = lgn$, so that the recurrence can be rewritten as follows: $S(m) = ...
0
votes
1answer
28 views

Is $f(n) + O(f(n)) = \theta(f(n))$?

I've been asked to show whether this is always, never or sometimes true. I think I understand that in this situation, $O(f(n))$ can be treated as a macro for some function $g(n)$. So if the equation ...
0
votes
0answers
21 views

Max Function Notation [duplicate]

I've been asked whether the following is always, never or sometimes true: $f(n) + g(n) = \theta(\max(f(n), g(n)))$ I understand the definition of theta notation, but I'm not sure how to read the ...
2
votes
1answer
45 views

Time complexity of random algorithm

I was wondering how to perform the complexity analysis of the following random algorithm. The answer are: $\Omega(n)$, $O(n²)$, and $\Theta(n)$. At first I thought to perform the analysis by saying ...
-2
votes
1answer
47 views

Prove that $\log n = O(\log^2 n)$

Trying to solve this, but I can't seem to figure it out. Its fairly straight forward.
1
vote
1answer
30 views

Proving an asymptotic run time is faster than another using L’Hôpital’s

I'm working on a problem: Show using L’Hôpital’s Rule that a running time of $n\log(n)$ is asymptotically faster than (i.e., little-oh of) a running time of $\frac{n^2}{\log(n)}$.` I suppose a ...
2
votes
2answers
49 views

Master theorem - why the log factor?

I think I finally managed to fully understand the master theorem but there's one thing left in the second clause (I'm following here: ...
4
votes
1answer
44 views

Problem understanding Master theorem

I'm studying the Master theorem (for the analysis of recursive algorithms) and I perfectly understand why a binary search is of order $\log_2(n)$. I also understand that if we formulate it as $T(n) ≤ ...
0
votes
2answers
243 views

How to arrange functions in increasing order of growth rate , providing f(n)=O(g(n))

Given the following functions i need to arrange them in increasing order of growth a) $2^{2^n}$ b) $2^{n^2}$ c) $n^2 \log n$ d) $n$ e) $n^{2^n}$ My first attempt was to plot the graphs but it didn't ...
2
votes
0answers
39 views

Prove that (x+1)! is not O(x!)

Discrete math question which is as follows: Prove that (x+1)! is not O(x!) using only the definition of Big-Oh notation. (Hint!: log(a * b) = (log a + log b)) I used a proof by contradiction saying ...
1
vote
1answer
27 views

If $p(x)$ is a polynomial of degree d, prove that $p(x) \in \Theta(x^d)$

I just started learning asymptotic notation and I have a problem with this one. Let $p(x)=a_dx^d+a_{d-1}x^{d-1}+.....+a_1x+a_0$ be a polynomial of degree d, with $a_i \in \mathbb{R}$ for $0\leq i ...
1
vote
1answer
44 views

Given a set $S$, find any $N$ numbers than sum to $X$

Similar but different from the problem here. I have an unsorted set $S$ of real numbers, and need to sum elements from $S$ to find the real number $X$; However, It could be from $1$ to $N$ elements ...
0
votes
1answer
26 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
28 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
60 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
1answer
87 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
35 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
48 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
73 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
45 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
77 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
262 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
95 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
40 views

Calculating algorithmic complexity

Given the following bit of code, how would I calculate the complexity? ...
1
vote
2answers
152 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
126 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
40 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
57 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
29 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
2answers
489 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
101 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
160 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
58 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
87 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
22 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
118 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
67 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
48 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
1answer
202 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
85 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
60 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
1k 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
69 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
103 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
101 views

Running time of a function of n with while loop

Provide a tight Θ bound on the running time of the function of n. ...