# Tagged Questions

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 ...
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.
21 views

### Time Complexity of one Challenging Example

Anyone would help me to calculate the order (time complexity) of this example ?
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 ...
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. ...
23 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})$?
55 views

### Show that $\frac{x^4 +7x^3+5}{4x+1}$ is big-theta($x^3$)

I'm having trouble grasping how to set these types of problems. There are a lot of related questions but it's difficult to abstract a general procedure on finding constants that give the given ...
49 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 ...
57 views

### Asymptotic approximation of binomial theorem

Binomial theorem is a very popular theorem that: $$(x + y) ^ n = \sum_{i=0}^n {n \choose i}x^i y^{n-i}$$ I am looking for any papers (the newer the better) where I can find any informations about ...
53 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: ...
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 ...
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 ...
76 views

### Easy Proofs with Functions and Big-O

I have these two questions. I tried answering them, but got them wrong and I don't know how to answer them correctly. This is not homework --- I'd appreciate a solution (at least to one), and an ...
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 ...
377 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 ...
136 views

### The result of O(f(n)) - O(f(n))

My question is in the field of the big-O-notation and complexity/asymptotic functions: Probably something that I'm missing, but I've couldn't find any well explained solution for the following: What ...
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 ...
528 views

### Big O notation - Proving that a function is not O(n)

Show that the function, $T(n) = 4n^2$ is NOT $O(n)$. I'm not looking for someone to give me a full answer, I just need some pointers on how to go about starting to show that it is not $O(n)$. Many ...
128 views

### Algorithm Analysis: How to simplify a summation leading up to a maximal term?

Okay so I have a summation which goes: $$\sum_{i=1}^{n^3} 3i^2\cdot\log(i)$$ My goal is to find the order of the function, not the exact summation amount. I have found the order of it by writing ...
39 views

### How to check if a function is negligible?

Let $\epsilon(x)$ be a negligible function. Let $p$ be a polynomial such that $p(k) \geq 0$ for all $k > 0$. What can we say about $\epsilon(p(k))$? Is this a negligible function? If yes, ...
72 views

### Does proving that a function is not in big O mean that the function is in big Omega?

If I determine that a function is not in Big O of another function, can you assume that the function is in big Omega of the same function?
31 views

441 views

### Prove that $1 + \dfrac{1}{2} + \dfrac{1}{3} + \cdots + \dfrac{1}{n} = \mathcal{O}(\log(n))$.

Prove that $1 + \dfrac{1}{2} + \dfrac{1}{3} + \cdots + \dfrac{1}{n} = \mathcal{O}(\log(n))$, with induction. I get the intuition behind this question. Clearly, the given function isn’t even growing ...
85 views

### What is a basic definition for Big Oh, and it's component parts?

this is a question that somewhat straddles the boundaries of computer science (data structures and ). I'm mostly fine with data structures, until encountering big oh notation.. at which point my head ...
764 views

### Formally prove that $\Theta(\max(f,g)) = \Theta(f+g)$

I am having a hard time proving that $\Theta(\max(f,g)) = \Theta(f+g)$ where $(f+g)(n) = f(n) + g(n)$ and $(\max{f,g})(n) = \max(f(n), g(n))$ I know that $\Theta$ is the combination of the ...
84 views

### Asymptotic analysis for multiple variables?

How is asymptotic analysis (big o, little o, big theta, big theta etc.) defined for functions with multiple variables? I know that the Wikipedia article has a section on it, but it uses a lot of ...
64 views

### Asymptotic constants for a quadratic?

Note than $n$ is a parameter for the functions. For some constants $c_1, c_2$ and $n_0,$$c_1n^2\le an^2 + bn + c \le c_2n^2$$ for all n >$n_0$. Consider any quadratic function$f(n) =an^2 ...
2k views

### Big-O notation Basics, is it related to derivatives?

I am having the hardest time with Big-O notation (I am using this Rosen book for the class I am in). On the surface, Big-O reminds me of derivatives, rate of change and what not; is this proper ...
142 views

### Is $O(n^2) = O(n^3)$? Prove your answer.

I am not sure how to go about doing this, I know that: $$O(g(n))=\{f : \exists \ c \ \in \Bbb R_+, \ \exists \ n_0 \in \Bbb N, \ \forall \ n\geq n_0 :f(n) \le c·g(n)\},$$ but how do I go about using ...
42 views

### Asymptotic analysis of a ratio

Is $\frac{n^2}{n-2}\in O(n)$ true? Intuitively it seems so but how would I rigorously prove this?
I want to establish a Big-O estimate for the following: $$(n! + 2^{n+3})(111n^3 + 15\log(n^{201} +1))$$ Would the following be correct? $n! = O(n^{n})$ $2^{n+3}=O(2^{n+3})$ $111n^{3}=O(n^{3})$ ...