Please help and explain to help me understand.. Give one operation, on a Python
ID: 3856899 • Letter: P
Question
Please help and explain to help me understand..
Give one operation, on a Python list, which takes O(1) time. Then give one operation which takes O(n) time. A classic example function, for intro programming classes, is one that determines whether a number is prime. A simple version checks to see if the number, n, is divisible by all other numbers, which runs in O(n) time: def is_prime(n): for d in range(2, n): if n % d == 0: return False return True Suppose that we make a simple change, by only checking 2, and then odd numbers. (Do not bother with writing this code out.) How does this change effect the asymptotic (that is, big-Oh) time cost? Explain your answer.Explanation / Answer
Python list has many O(1) and O(n) operations like
let L1=[1,2,3,4,5]
O(1) index example L1[i]
O(1) pop example L1.pop()
O(n) reverse example L1.reverse()
O(n) delete example del L1[2]
3. If you check using 2 and odd numbers upto n then the time complexity reduces by half since for half of n loop is iterated. the time complexity is O(n/2)
Code:
def is_prime(n):
if n%2==0:
return False
start=3
while(start<n):
if n%start==0:
return False
start=start+2
return True
Same can be seen here in the code.