algorithm question

[hider]

1- A certain algorithm takes twice as long to process 1000n elements as it does to process n elements. Give a possible time complexity for this algorithm and a specific value of n

2- A certain O(nlogn) algorithm is always used in practice over an available O((logn)^2) algorithm

1 - is it on^2

2 - ?

please help

thanx

[Rashakil Fol]

#1: Are you just guessing? The answer is yes, but it also is no.

#2: This is a question?

[hider]

hi

well for question 1 i thought because its quadric so it should take double time.. i am not sure can you please help.

for question 2 yes its a question from last year midterm and i am not sure how to answer it.

i am doing review for last year midterm and final.

thanx

[Rashakil Fol]

The first question could have multiple answers.

Assuming they meant "for all n", the answer is definitely not quadratic. The runtime doubles, but only when the input size multiplies by one thousand! If it were quadratic, the runtime would double when the input size multiplies by 1.414. Just find the ration of n^2 to (1.414n)^2.

Generally, we have the relationship: f(1000n) = 2 f(n). What functions fit that relationship?

It grows a lot slower than quadratic. This means that the function is in O(n^2). But it also happens to be in O(n), and some even smaller bounds. (For being in O(n^2) means that the function grows no faster than n^2. If f(x) = x, then f(x) is in O(x^2).)

One function that fits the first equation is f(n) = n^(0.010034333189).

Because then, f(1000n) = 1000^(0.010034333189) * n^(0.010034333189) = 2*(n^0.010034333189) = 2 f(n).

If that relationship they gave only applies to a specific value of n, and not all values of n, well, then you could fit almost any type of function to those two data points. You could let f(n) = 2^n. Then at the point n = 1/999, it would be true that f(1000n) = 2 f(n), and it would not be true anywhere else.

I don't know if this is all very relevant to your exam, but that's my take on the first question.

The second is not even a question or problem, it's just a statement of fact. Is it a true/false?

[hider]

question nice and clear answer thanx much

for question 2 sorry its like that

- an O(n)algorithm is always faster tan an O(n*n)algorithm for all n>1. True or false? explain

[Rashakil Fol]

f(n) = n + 1000
g(n) = n*n