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.