-1

For each function f(n) and time t, determine the largest size n of a problem that can be solved in time t,

where f(n)=t sec.

For the above question, I have to solve for f(n)=nlogn that means nlogn=t

how to find out the value of n, from above equation..?

Igniter
  • 565
  • 1
  • 4
  • 13
  • This is not a HW site. Especially not math HW... – shapiro yaacov Sep 07 '15 at 12:49
  • 1
    You need the [Lambert W function](https://en.wikipedia.org/wiki/Lambert_W_function) aka the "product log". – Paul R Sep 07 '15 at 12:50
  • I am doing excercise from my book, it is not HW. I just want to learn how to solve these type of equations.. – Igniter Sep 07 '15 at 13:09
  • 1
    The question has also been discussed [here](http://math.stackexchange.com/questions/211922/how-to-get-value-of-n-if-the-value-of-n-log-n-is-given). – Codor Sep 07 '15 at 13:50
  • @Codor that is not the same equation OP needs to have function on one side not constant (OP is written a bit misleadingly) – Spektre Sep 08 '15 at 06:32
  • @Igniter what do you know about `f(n)`? how do you want to approach this (algebraically (mostly not doable depends on the f(n)),numerically, approximately,...) What are the solution constrains (numbers range,computation time,accuracy) – Spektre Sep 08 '15 at 06:35
  • I'm voting to close this question as off-topic because it seems to be a question of mathematics. – High Performance Mark Sep 08 '15 at 12:22

1 Answers1

0

If it is a programming question, I'd solve it using binary search on n ranging from 1 to t (as low and high in the beginning). If n*log(n) on midvalue exceeds t, bring high to mid else set low to mid and viola.

And if it is a maths question, I'd advice you to post it to mathematics.stackexchange community.

vish4071
  • 5,135
  • 4
  • 35
  • 65
  • binary search is usable only if `f(n)` is monotonous as OP does not provide any info about it better choice would be approximation search something like this [see approx class in C++](http://stackoverflow.com/q/29166819/2521214) with small enough initial step – Spektre Sep 08 '15 at 06:24
  • @Spektre, Why do you say so? Isn't `n log n` a monotonous function in itself? – vish4071 Sep 08 '15 at 09:53
  • `f(n)` is `n*log(n)` for `n` but is the `y=f(x)` monotonous ? I do not know as I have no clue what is behind `f(x)` and so you can not assuming it is ... – Spektre Sep 08 '15 at 13:40
  • n*log(n), which is our concerned function here, **is** monotonous and so we can apply binary search for `n` to find when `n log n = t` – vish4071 Sep 09 '15 at 05:58
  • you still not getting my concern. According to OP the `t` is function dependent on `n`. So while binary searching the value of searched `n` is changing so the `t` must changing too and that will mess up the binary search unless `t=f(n)` is monotonic on searched range too ... – Spektre Sep 09 '15 at 07:32
  • Are you serious?? Lets say, we need to solve for t=10 and let base of log be 10(for simplicity) and initial range be 1 to 80. So, 1st value will be 40. If we calculate 40log40 we set a value which is >t (10 in this case) So we bring our value down to 20 and calc 20log20 which is again >t. Now when n=10, we get our solution as 10log10 = 10 =t. – vish4071 Sep 09 '15 at 07:39
  • How does calculating n*log(n) affect `t`? `t` is a constant value that we need to get at the end of the day. – vish4071 Sep 09 '15 at 07:40
  • for example what if `f(n)=tan(n)` when you set `n=10` then you are computing `10*log(10)=tan(10)` if you change `n=20` then you are computing `20*log(20)=tan(20)` and so on... as `f(n)` can be any arbitrary function/equation dependent on `n` YOU CAN NOT HANDLE IT AS CONSTANT !!! – Spektre Sep 09 '15 at 07:43
  • Ok. I get it, but here, question says **f(n)=t sec**, and clearly **f(n)=n log(n)**. So, that is it. Also, if you are saying `t` is also an unknown and `n` also is, obvs, in that case it would be impossible because 2 unknowns cannot be solved in one eq. – vish4071 Sep 09 '15 at 08:31
  • OP most likely knows the `f(n)=t` but has not share it contents with us. even if it is in form of unknown function call returning the `t` this is still solvable by approximation search (minimizing `|n.log(n)-f(n)|`) as I propose in my first comment to you. If you choose small enough initial step (not to skip local `min` of minimizing problem) it would lead to solution. I solve such things all the time in RT for my work ... – Spektre Sep 09 '15 at 08:52