Tagged Questions

20 views

I see in some notes from my instructor in Algorithm course that $\Sigma_{i=0}^{log n} (n/2^i)$ has growth bigger than $\Sigma_{i=1}^{n} (i log i)$. i couldn't understand why? any tutorial or hint?
35 views

Big-Oh of exponent of exponent

How does one whether an exponent of an exponent is the big-Oh of the other? For example, if I have $a^{b^n}$ and $b^{a^n}$, how would i determine and prove which is a big oh of another? I'm thinking ...
22 views

Proving Algorithms

I'm trying to get down how to prove that something is $O(\cdots)$ or $\Theta(\cdots)$ but no matter what I look at, I don't get the reasoning as to how I can come to an answer. So here's a couple of ...
45 views

How to prove the $\Theta$ notation?

I know that to prove that f(n) = $\Theta$(g(n)) we have to find c1, c2 > 0 and n0 such that $$0 \le c_1 g(n) \le f(n) \le c_2 g(n)$$ I'm quite new with the proofs in general. Let assume that we ...
47 views

Using Big-O to analyze an algorithm's effectiveness

I am in three Computer Science/Math classes that are all dealing with algorithms, Big-O, that jazz. After listening, taking notes, and doing some of my own online searching, I'm pretty damn sure I ...
28 views

How can I find The Big Oh bounds for a summation with multiple variables?

I have this as a homework problem so I won't post the same thing. I'll just post what I need to know to move forward. $$\sum_{i=0}^n 10^i i^2$$ I'd just like to know how to split this ...
19 views

Using Limits to Determine Big-O, Big-Omega, and Big-Theta

I am trying to get a concrete answer on using limits to determine if two functions, $f(n)$ and $g(n)$, are Big-$O$, Big-$\Omega$, or Big-$\Theta$. I have looked at my book, my lecture notes, and have ...
39 views

How is $O(\log(\log(n)))$ also $O( \log n)$?

How is $O(\log(\log(n)))$ also $O( \log n)$? I have seen this result somewhere with this but I still didn't quite understand how this is true. This would also help me compute Big Omega of the ...
41 views

Find Recurrence Relation of Code

Suppose A(n) be the number of stars that wrote with the following example. for n>=3, i want calculate the recurrence relation for this code. any idea or solution? ...
32 views

The Basic Example and Output of Algorithms [closed]

if exg(x,y) swap the x,y, and array A contains integer numbers, the following algorithm how modify the $A[1]$ and what is the operation of the following algorithm? i confused to trace this code. any ...
28 views

Time Complexity of one Example Code

i see an example on my note for calculating Time Complexity, but i couldn't understand. anyone could help me.
51 views

Increasing Growth Rate Challenge [closed]

why from left to right, we have increasing in growth rate? any description for some usual equivalence formula for each of them?
36 views

Add two a,b bits number Algorithm

Suppose we want add two numbers that has a and b bits. we do such operation in O(max{a,b}). we want to add n, 1 bit numbers (0 or 1). what is the best and worst case of this algorithm? i ran into ...
37 views

Question about efficiency of an algorithm (Big-O)

The efficiency of the algorithm dolt can be expressed as O(n)=n^3.Calculate the efficiency of the following program segment exactly and by using the big-O notation. ...
26 views

Need an Algorithm Such that $\sum_{k-i}^{j}{A[k]}$

I need an algorithm for real application. Suppose we have array A (positive & negative ) numbers. we want to find index i, j such that $\sum_{k-i}^{j}{A[k]}$ has the lowest difference to zero. ...
24 views

Omega Notation and Average Running Time Problem

if we have an algorithm that average running time of randomized algorithm A for input of size n is equal to $\theta(n^2)$. why there would be an input data such that A solve it in $\Omega(n^{3n})$?
47 views

Big-O, Omega, Theta and Orders of common functions

Based on this table, is it generally going to be true that for two functions whose most "significant" terms are of the same order that they will be big-Theta each other? And a function of order ...
95 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 ...
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 ...
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 ...
28 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 ...
28 views

582 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 ...
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 ...
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 ... 1answer 50 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 ... 1answer 29 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 ... 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 ... 1answer 61 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 ... 2answers 33 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. ... 1answer 130 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 ... 1answer 41 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 ... 0answers 49 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 ... 1answer 106 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 ... 1answer 51 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 ... 2answers 80 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 ... 3answers 378 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 ... 1answer 100 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 ... 1answer 40 views Calculating algorithmic complexity Given the following bit of code, how would I calculate the complexity? ... 2answers 184 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. 2answers 144 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 ... 0answers 43 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 ... 2answers 59 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 ...
Given following recursive equation: $$T(n) = T(n-3) + \Theta(1)$$ Is it correct that this equation is O(1)?