1
$\begingroup$

Just finishing an investigation into Shor's algorithm, and the following equation, $$ O\big(\big(\log N\big)^2 \big(\log \log N\big)\big(\log \log \log N\big)\big) $$ is given for its time complexity. However, this is negative for most small values, becoming 0 at $1\cdot 10^{10}$.

Why is this?

Improve this question
$\endgroup$
2
  • $\begingroup$ This is only 34 bits. Try 2^{128} or for RSA 2^{2048} $\endgroup$
    – kelalaka
    Oct 14, 2018 at 19:43
  • 1
    $\begingroup$ I get a root @ $e^e$. Strange. Ah - natural logs. $\endgroup$
    – Paul Uszak
    Oct 14, 2018 at 21:49

1 Answer 1

Reset to default
4
$\begingroup$

The big O notations describes the complexity when $N$ approaching infinity, it is not a formula giving you exact running time for all $N$.

Roughly, let $f(N)$ be the function for the running time of the algorithm, the big O notation says that there exists $n$ and a constant $c$ such that $f(N)<c\cdot (\log N)^2(\log\log N)(\log\log\log N)$ for all $N>n$.

Improve this answer
$\endgroup$
1
  • $\begingroup$ And, as $n\rightarrow \infty $ equation $\rightarrow \infty$ $\endgroup$
    – kelalaka
    Oct 14, 2018 at 19:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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