If you want to make money online : Register now

[Solved]: Is it admited to give the complexity of a function regarding the resulting data structure?

, , No Comments
Problem Detail: 

Assume that we have a data structure which uses $O(\log n)$ space to store an integer $n$ and has a function $f$ which replaces the integer $n$ stored by $2^n$, i.e. $n=2^n$.

The time complexity of $f$ is $O(n_{_{old}})$ = $O(\log\ n_{_{new}})$, is it admited to say that $f$ is a $O(\log n)$ function ?

Asked By : François

Answered By : Yuval Filmus

The running time of a function is usually measured with respect to the length of the input, which is represented by the parameter $n$. In your case, if the input is the integer $m$ then the input length is $n = \log m$ and the running time is $O(m) = O(2^n)$.

For functions whose output is much larger than the input, it makes sense to measure the complexity with respect to the size of the output. In your case, the function runs in linear time with respect to the size of the output.

In other cases it might be meaningful to use other parameters to measure the running time of a function. For example, functions on graphs are sometimes measured with respect to the number of vertices and the number of edges. The end goal is usually to analyze the running time of some function in terms of its input length, but on the way it is OK to measure the running time of subroutines in terms of other parameters.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/55954

 Ask a Question

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback