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)?
Thank's
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.
