# Runtime for algorithm

I need to get the asymptotic runtime for an algorithm and I'm just stuck.

A python implementation:

def alg3(n):
for i in range(1, n+1):
for j in range(1, n+1):
k = j
while k <= n:
k = k*3


I think it should somehow be $\Theta(n^2\log(n))$ but that isn't quadratic. Can you help?

import time

def alg3(n):
count = 0
for i in range(1, n+1):
for j in range(1, n+1):
k = j
while k <= n:
count = count + 1
k = k*3
print(count)

n = 10
for i in range(0, 6):
start_time = time.time()
# run two times then calculate average time
for i in range(0, 100):
alg3(n)
print("time with size %s: %s seconds" % (n, (time.time() - start_time)/100))
n = n*2


If you calculate the factors given they give about 4.1.

• Have you tried it with n such that {there exists a positive integer m such that ​ 3^m ≤ n ​ and 3^m doesn't fit in a machine word}$\hspace{.02 in}$? ​ ​ ​ ​ – user12859 Feb 28 '16 at 15:22
• 1) Please transcribe the algorithm using Markdown. 2) Experiments can never prove asymptotics. 3) Our reference question can help you do the analysis. – Raphael Feb 28 '16 at 17:40
• What is the question here? "Can you help?" is too broad a query. Community votes, please! – Raphael Feb 28 '16 at 17:40

Let $f(n) = n^2\log n$, with the $\log$ taken to base 2. Then $$\frac{f(2n)}{f(n)} = 4 \frac{\log(2n)}{\log n} = 4 \left(1 + \frac{1}{\log n}\right).$$ That is, for large $n$ you would expect $f(2n) \approx 4f(n)$. This shows that this test isn't sensitive enough to detect logarithmic factors.
Let $f$ be the runtime of your algorithm, it's easy to find a close form $$f(n) = n \sum_{j=1}^n \log_3 \left\lceil \frac{n}{j}\right\rceil$$
Then some calculations, \begin{aligned} f(n) &\leq n + \frac1{\ln 3} n \sum_{j=1}^n \ln (\frac{n}{j}) \\ &\leq n + \frac1{\ln 3} n \int_{0}^{n} \ln (\frac{n}{x}) \mathrm{d}x \\ &= n + \frac1{\ln 3} n^2 \end{aligned}
Similarly, you can lower bound $f$.
$f(n) = \frac1{\ln 3} n^2 + O(n)$.