0

I am wondering if there is a straight forward way to illustrate the proportional growth rate in time (or space) for any given notation such as $O(n^2)$ or $O(logn)$?

My initial thought is that $O(n^2)$ would be equal to $O(n)*O(n)$ but I'm sure that's completely wrong.

Switchkick
  • 103
  • 1
    I'm not sure, what you mean. In fact, $O(n^2)=O(n)\cdot O(n)$, i.e. every fucntion $f\in O(n^2)$ can be written as $f=gh$ with $g,h\in O(n)$. – Hagen von Eitzen Jun 04 '13 at 09:19
  • @HagenvonEitzen to tell you the truth, the question I'm trying to solve is super vague too: "The notation O(n3) means that its algorithm’s time (or space) growth rate is proportional to ______." – Switchkick Jun 04 '13 at 09:51

1 Answers1

1

We say that $f(n)=O(g(n))$ iff:

There exist constants $c,n_0$ such that for all $n\ge n_0$, if $c>0$, then $0 \le f(n) \le c \cdot g(n)$.

Also, recall that $y$ is proportional to $x$ simply if $y=kx$ for some constant $k$.

Thus, suppose some algorithm had a running time of $f(n)=O(n^3)$. Then we can conclude that this algorithm's (time or space) growth rate is proportional to $n^3$. For example, it might be the case that $f(n)=4n^3$ or $f(n)=50n^3$.

Adriano
  • 41,576