I want to analyze a clustering algorithm that clusters data stream. Since the stream can be unbounded, I cannot write O(N^2), or explicitly denote the size of the stream. How can I use the arrival rate of the data for the computation complexity? Do you have any other idea for correct analysis of stream computation (for clustering problems)?


  • $\begingroup$ In final analysis, your algorithm computation complexity depends on what? What is your computation complexity per new arrived item? This will give you the time complexity per N-items arrived till now or in total, if this is the maximum stream length. (It is just a multiplication) $\endgroup$ – Curious_Dim Jan 25 '18 at 16:07
  • $\begingroup$ I can't understand what exactly your question is. I suggest you do some background reading about streaming algorithms and online algorithms (e.g., en.wikipedia.org/wiki/Streaming_algorithm) and then see if you can formulate a more specific question. Those fields certainly measure the running time of algorithms. $\endgroup$ – D.W. Jan 25 '18 at 18:30

One standard way to measure the running time of streaming algorithms is to count the amount of time taken per item that the algorithm processes. For instance, one algorithm might take $O(1)$ time per item.

Also it is common to analyze the memory usage (space complexity) of these algorithms, as in many practical situations memory can be a limiting factor. That is straightforward to measure. Usually the space complexity is measured not as a function of the number of elements seen, but rather as a function of something else -- e.g., the accuracy of the answer, or the number of distinct items in the input stream, or something else that is appropriate to the application and that makes it possible to do analysis.

I suggest you read about streaming algorithms. There's lots of work on those topics and those fields certainly measure the running time of their algorithms. See, e.g., https://en.wikipedia.org/wiki/Streaming_algorithm and textbooks on the subject.

| cite | improve this answer | |

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.