Question

PYTHON: Im stuck here, big O notation and runtime. What is it and Why are they those? Please look at the pic, need help as Im confused. Thank You!

def method3(n): for i in range(n): for j in range(100): for k in range(n): print(i+j+k) What is the runtime (tightest/closest bound in terms of O) for the above python function (method 3)? Please briefly explain. Enter your answer here def method4(n): for i in range(n): for j in range(n, o, -2): print("hi") x = 0 while x <n: X += 1 print("hello") What is the runtime (tightest/closest bound in terms of O) for the above python function (method4)? Please briefly explain. Enter your answer here

Answer 1

1.

Ans: O(100 *n²)

1 2 def method3(n): for i in range(n): # here this will run 'n' times for j in range (100): # here this will run exactly 100 times for k in range(n): # here this will run 'n' times print(i+j+k) # this is constant time 4 5 6 7 8 9 # overall running time= (n*100*n)+constant =100*n^2 +constant =0(100(n^2)). # note here in assymtotic notation only higher order terms are considered. # Because the rate of growth of higher order terms is high compared to lower order terms.

2.

Ans: O(n²/2)

1 def method4(n): 2 for i in range(n): # this will execute 'n' times 3 for j in range(n,0,-2): # this will execute 'n/2' times 4 print("hi") # this will take constant time 5 6 X=0 7 while x<n: # this will execute 'n' times 8 X+=1 # this will tske constant time 9 print("hello") # this will take constant time 11 # overall running time= ((n*(n/2)+constant) + (n+constant+constant) =h^2 /2 +n =0 (|(n^2)/2) # note here in assymtotic notation only higher order terms are considered. # Because the rate of growth of higher order terms is high compared to lower order terms. 10 12 13