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.