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$
  • $\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 '16 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 '16 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 '16 at 17:40
5
$\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$
4
$\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, privacy policy and cookie policy

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