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


11 Years
Discussion Span
Last Post by Rashakil Fol


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.



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?


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

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.