0
$\begingroup$

I am new to all of this and I am trying to understand how to define Time Complexity. I have an algorithm which performs a set of operations on inputs of different size.

While timing the execution of such algorithm I have figured out that the time elapsed follows an exponential law:

Time(size)=0.15*exp(0.05*size)

My question: is it correct to define this complexity according to

T(n)=O(e^n)?

$\endgroup$
8
  • $\begingroup$ No, since for example, $\;\;\; e^{\hspace{.02 in}2\cdot n} \: = \: e^{\hspace{.02 in}n+n} \: = \: e^{\hspace{.02 in}n}\hspace{-0.04 in}\cdot \hspace{-0.04 in}e^{\hspace{.02 in}n} \: \not\in \: O(e^{\hspace{.02 in}n}) \:\:\:\:$. $\;\;\;\;\;\;\;\;$ $\endgroup$
    – user12859
    Commented Apr 27, 2016 at 16:15
  • $\begingroup$ Ok, and how should I describe this trend? Could it be n*O(e^n)? $\endgroup$
    – FaCoffee
    Commented Apr 27, 2016 at 16:17
  • 1
    $\begingroup$ @RickyDemer But $0.15 \mathrm{e}^{n/20}$ is in $O(\mathrm{e}^n)$. $\endgroup$ Commented Apr 27, 2016 at 16:50
  • 1
    $\begingroup$ Note that "time complexity" is not measured in seconds and, while you can approximate it from timing measurements, to find out what the time complexity is, you must analyse the algorithm, not use a stopwatch. "Time", in this sense, refers to computation steps, not seconds. $\endgroup$ Commented Apr 27, 2016 at 16:53
  • 1
    $\begingroup$ @FC84 See here, here and here. So no, don't even try. Do a proper analysis. On a more constructive note, how many models did you fit against your measurements, with how many parameters each? How did you decide to prefer one fit over another? $\endgroup$
    – Raphael
    Commented Apr 28, 2016 at 11:37

1 Answer 1

1
$\begingroup$

It depends on whether you're talking about $O$ or $\Theta$. The notation $O$ indicates that the complexity is "this much or smaller", and the notation $\Theta$ indicates that the complexity is "this much, no more or less".

The complexity of $0.15 e^{0.05 n}$ is $\Theta(e^{0.05 n})$. The complexity is not $\Theta(e^n)$, because $e^n$ grows faster than $e^{0.05 n}$ does (the ratio between the two increases without bound).

It is, in fact, true that $0.15 e^{0.05 n}$ is an $O(e^n)$ function, but this isn't a good description of the complexity, in much the same way that "more than a thousand people live in China" is not a good description of the population of China.

What this comes down to is that you should state the complexity as $\Theta(e^{0.05 n})$ or as $O(e^{0.05 n})$.

$\endgroup$
5
  • $\begingroup$ Also, given that the value 0.05 is only empirically measured, I would argue that it is not correct to claim that the complexity is $O(\mathrm{e}^{0.05n})$. It's perfectly within the realm of experimental error that the true answer is $0.14\mathrm{e}^{0.055n}$, which is still $O(\mathrm{e}^n)$ but is not $O(\mathrm{e}^{0.05n})$. (And this is putting aside the whole issue of not being able to measure time complexity with a stopwatch.) $\endgroup$ Commented Apr 27, 2016 at 21:40
  • $\begingroup$ @DavidRicherby I've edited my answer; you might like the new version a little better. $\endgroup$ Commented Apr 27, 2016 at 22:46
  • 1
    $\begingroup$ Definitely better, yes. But I still take issue with statements such as "It is, in fact, true that the complexity of your algorithm is an $O(e^n)$ function", since empirical measurements can never demonstrate that. And empirical measurements certainly can't support a claim of $\Theta(\mathrm{e}^{0.05n})$. $\endgroup$ Commented Apr 27, 2016 at 22:53
  • $\begingroup$ So @DavidRicherby you have provided me and us with a number of points but what is your answer? $\endgroup$
    – FaCoffee
    Commented Apr 28, 2016 at 11:35
  • $\begingroup$ @CF84 My answer is that the question contains a category error, as I explained in my first comment below the question. You cannot measure time complexity with a stopwatch, so you can't deduce anything for sure about the time complexity from your measurements. $\endgroup$ Commented Apr 28, 2016 at 14:56

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