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}$. I was wondering why this is?

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

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$.

  • $\begingroup$ And, as $n\rightarrow \infty $ equation $\rightarrow \infty$ $\endgroup$ – kelalaka Oct 14 '18 at 19:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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