0
$\begingroup$

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

Algorithm

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.

$\endgroup$
3
  • $\begingroup$ 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}$? ​ ​ ​ ​ $\endgroup$
    – user12859
    Feb 28, 2016 at 15:22
  • 2
    $\begingroup$ 1) Please transcribe the algorithm using Markdown. 2) Experiments can never prove asymptotics. 3) Our reference question can help you do the analysis. $\endgroup$
    – Raphael
    Feb 28, 2016 at 17:40
  • 1
    $\begingroup$ What is the question here? "Can you help?" is too broad a query. Community votes, please! $\endgroup$
    – Raphael
    Feb 28, 2016 at 17:40

2 Answers 2

4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$

Your Answer

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

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