Consider The problem of determining whether an arbitrary sequence [x1,x2,...,xn] of n numbers contains repeated occurrences...

Question

Question

Consider The problem of determining whether an arbitrary sequence [x1,x2,...,xn] of n numbers contains repeated occurrences...

Consider The problem of determining whether an arbitrary sequence [x1,x2,...,xn] of n numbers contains repeated occurrences of some number. Show that this can be done in O(nlogn) time.

engineering Computer-Science

Add a comment Improve this question Transcribed image text

Answer 1

Answer #1

Yes, this can be done in O(nlogn) time.

lets see

first those n numbers using merge sort (which will take O(nlogn) time )

then traverse the sorted sequence using for loop, and compare adjacent elements (takes O(n) time)

if any two adjacent elements are equal, means we have found a repeated occurrence

if we don't find then there are no repeated occurrences

total complexity : n+nlogn = O(nlogn)

Add a comment

Answer 2

Similar Homework Help Questions

Let X = x1, x2, . . . , xn be a sequence of n integers....

Let X = x1, x2, . . . , xn be a sequence of n integers. A sub-sequence of X is a sequence obtained from X by deleting some elements. Give an O(n2) algorithm to find the longest monotonically increasing sub-sequences of X.
given a size N, create a row vector x= [x1,x2,....,xN] which contains the first N terms...

given a size N, create a row vector x= [x1,x2,....,xN] which contains the first N terms of the below sequence: x1=2 xi+1=3-xi you must use a for loop to generate the elements in x. this is done in MATLAB
Consider a sequence of random variables X1, ..., Xn, ..., where for each n, Xn~ tn....

Consider a sequence of random variables X1, ..., Xn, ..., where for each n, Xn~ tn. We will use Slutsky's Theorem to show that as the degrees of freedom go to infinity, the distribution converges to a standard normal. (a) Let V1, ..., Vn, ... be such that Vn ~ X2. Find the value b such that Vn/n þy b. (b) Letting U~ N(0,1), show that In = ☺ ~tn and that Tn "> N(0,1). VVn/n

Let X1, X2,...be a sequence of random variables. Suppose that Xn?a in probability for some a...

Let X1, X2,...be a sequence of random variables. Suppose that Xn?a in probability for some a ? R. Show that (Xn) is Cauchy convergent in probability, that is, show that for all > 0 we have P(|Xn?Xm|> )?0 as n,m??.Is the converse true? (Prove if “yes”, find a counterexample if “no”)
Problem 5: 10 points Consider n independent variables, {X1, X2,... , Xn) uniformly distributed over the...

Problem 5: 10 points Consider n independent variables, {X1, X2,... , Xn) uniformly distributed over the unit interval, (0,1) Introduce two new random variables, M-max (X1, X2,..., Xn) and N -min (X1, X2,..., Xn) 1. Find the joint distribution of a pair (M,N) 2. Derive the CDF and density for M 3. Derive the CDF and density for N.
Problem 10. Let X1, X2, . . . be random variables such that Xn → c...

Problem 10. Let X1, X2, . . . be random variables such that Xn → c in D holds for some number c. Show that Xn → c in P holds

R CODE: 1. A bag contains n distinct (all different) numbers: (x1; x2; : : :...

R CODE: 1. A bag contains n distinct (all different) numbers: (x1; x2; : : : ; xn) . Per- son A draws a number at random, while person B draws a number from the remaining choices. What is the exact probability that A's number is greater than B's number? Explain your reasoning in detail.
5. Let {xn} and {yn} be sequences of real numbers such that x1 = 2 and...

5. Let {xn} and {yn} be sequences of real numbers such that x1 = 2 and y1 = 8 and for n = 1,2,3,··· x2nyn + xnyn2 x2n + yn2 xn+1 = x2 + y2 and yn+1 = x + y . nn nn (a) Prove that xn+1 − yn+1 = −(x3n − yn3 )(xn − yn) for all positive integers n. (xn +yn)(x2n +yn2) (b) Show that 0 < xn ≤ yn for all positive integers n. Hence, prove...
Consider a sequence of random variables X1, . . . , Xn, . . .where for each n, Xn ∼ t distributio...

Consider a sequence of random variables X1, . . . , Xn, . . .where for each n, Xn ∼ t distribution. Apply Slutsky’s Theorem to show that as the degrees of freedom go to infinity, the distribution converges to a standard normal. (a) Let V1, . . . , V_n, . . . be such that Vn ∼ Chi Sq, n df. Find the value b such that V/n in probability −→ b. (b) Letting U ∼ N(0, 1),...

σ2). 6. Suppose X1, Yİ, X2, Y2, , Xn, Y, are independent rv's with Xi and Y both N(μ, All parameters μί, 1-1, ,n, and σ2 are unknown. For example, Xi and Yi muay be repeated measurements on a lab...

σ2). 6. Suppose X1, Yİ, X2, Y2, , Xn, Y, are independent rv's with Xi and Y both N(μ, All parameters μί, 1-1, ,n, and σ2 are unknown. For example, Xi and Yi muay be repeated measurements on a laboratory specimen from the ith individual, with μί representing the amount of some antigen in the specimen; the measuring instrument is inaccurate, with normally distributed errors with constant variability. Let Z, X/V2. (a) Consider the estimate σ2- (b) Show that the...

Consider The problem of determining whether an arbitrary sequence [x1,x2,...,xn] of n numbers contains repeated occurrences...

Homework Answers

Add Answer to:
Consider The problem of determining whether an arbitrary sequence [x1,x2,...,xn] of n numbers contains repeated occurrences...

Post as a guest

Earn Coins

Let X = x1, x2, . . . , xn be a sequence of n integers....

given a size N, create a row vector x= [x1,x2,....,xN] which contains the first N terms...

Consider a sequence of random variables X1, ..., Xn, ..., where for each n, Xn~ tn....

Let X1, X2,...be a sequence of random variables. Suppose that Xn?a in probability for some a...

Problem 5: 10 points Consider n independent variables, {X1, X2,... , Xn) uniformly distributed over the...

Problem 10. Let X1, X2, . . . be random variables such that Xn → c...

R CODE: 1. A bag contains n distinct (all different) numbers: (x1; x2; : : :...

5. Let {xn} and {yn} be sequences of real numbers such that x1 = 2 and...

Consider a sequence of random variables X1, . . . , Xn, . . .where for each n, Xn ∼ t distributio...

σ2). 6. Suppose X1, Yİ, X2, Y2, , Xn, Y, are independent rv's with Xi and Y both N(μ, All parameters μί, 1-1, ,n, and σ2 are unknown. For example, Xi and Yi muay be repeated measurements on a lab...

Consider The problem of determining whether an arbitrary sequence [x1,x2,...,xn] of n numbers contains repeated occurrences...

Homework Answers

Add Answer to: Consider The problem of determining whether an arbitrary sequence [x1,x2,...,xn] of n numbers contains repeated occurrences...

Post as a guest

Earn Coins

Add Answer to:
Consider The problem of determining whether an arbitrary sequence [x1,x2,...,xn] of n numbers contains repeated occurrences...