2
$\begingroup$

I have two client-server protocols which perform the same function but they have different complexities in time (in terms of number of operations) and space (in terms of number of objects of same type). The size on which are based the complexities is $n$.

  • In the fist one, the server has to send only one object and the client has to perform $n$ operations.

  • In the second one, the server has to send $\log n$ objects and the client has to perform $\log n$ operations.

What is the best algorithm ? Does it depend on the environment of execution ?

$\endgroup$
2
  • 3
    $\begingroup$ There never is a single "best" algorithm. Which criteria do you have in mind? Even time and space usage are usually orthogonal. $\endgroup$ – Raphael Jun 2 '15 at 10:39
  • 1
    $\begingroup$ Maybe the best is the algorithm that uses less bandwidth, or the algorithm that uses globally less energy, Actually, your problem is not an issue of space, but of bandwidth (assuming, as you seem to be doing that all objects have the same size). All you are saying is that objects have to be sent, not that they have to be stored or remembered in any way. There is no memory issue in your question. $\endgroup$ – babou Jun 2 '15 at 15:32
3
$\begingroup$

The best algorithm must certainly depend on the environment. What type of system is your client? What type of system is your server? What kind of transport system stands between them?

If, for example, your clients are Raspberry Pis then it is likely you want to reduce the amount of work you need to do on the client end - take the log(n) option.

If, your client is a Mars Rover you want to minimise the amount of data you need to send and minimise the computation required at the client. Perhaps use the log(n) option, perhaps not - depends on the cost of transporting the data and the computation cost at the other end.

If, however, your server is the LHC then use the n approach - you have probably the largest data bandwidth on the planet and the least amount of time to offload that data you've just collected.

$\endgroup$
1
$\begingroup$

First, let me point out that there is no obvious memory issue in your question, only bandwidth. Nowhere is it written that objects (supposed to be the same size and same transmission cost, which you should make precise) have to be stored or remembered. But they clearly have to be transmitted.

It all depends on the load and the computing/transmission power of server and clients, on whether they are homogeneous or heterogeneous, and on the size distribution of the communication.

You may well want to mix the two protocols, and choose which to use for each transmission task, based on size of the task, on current load, and currently available power of the server and client(s).

$\endgroup$
0
$\begingroup$

A direct answer is: try to find an algorithm with small runtime.

Small data storage is not so important because the physical storage equipment's got very cheap and grate in amount.

Take care on accessibility of these storage devices. A lot of time gets lost for transport of data from the external storage to central main storage. All storage and load activities should work parallel.

Besides: why do you make a difference between n and log n? Mathematically they are only different numbers by value.

$\endgroup$
0
$\begingroup$

What you need to determine is not space and time, but cost. AND you may decide based on the cost that is relevant to you - if you pay for the server, but someone else pays for the clients, then you pick what is cheapest for the server.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.