How would I go about telling if my code runs on O(N) time (linear time?) or O(N^2) time or something else? Practice tests online dock points for codes that take to long to compute.
I understand that it is best to have a script in which the time it takes to run is proportional to the length of input data only ( O(N) time ), and I am wondering if that is what my code is doing. And how could one tell how fast the code runs?
Below I included a script I wrote that I am concerned about. It is from a practice exam problem in which you are given a series of 'a's and 'b's and you are to compute the palindromes. So if you are given s = "baababa", there are 6 palindromes: 'aa', 'baab', 'aba', 'bab', 'ababa', & 'aba'.
def palindrome(s):
length = len(s)
last = len(s)-1
count = 0
for index, i in enumerate(s):
left=1
right=1
left2=1
right2=1
for j in range(0,index+1): #+1 because exclusive
if index-left2+1>=0 and index+right2<=last and s[index-left2+1]==s[index+right2]:
print s[index-left2+1:index+right2+1] #+1 because exclusive
left2 +=1
right2 +=1
count +=1
elif index-left>=0 and index+right<=last and s[index-left] == s[index+right]:
print s[index-left:index+right+1] #+1 because exclusive
left += 1
right +=1
count += 1
return count
Is this O(N) time? I loop through the entire list only once but there is a smaller loop as well...
it's O(N^2). You have one loop from 0 to N and second loop goes from 0 to i. Let's see how much operations you have to perform. For each 'i' we look at the size of the list for j from 0 to i + 1 (let's take N = 7):
i = 0 | x x _ _ _ _ _ _ -
i = 1 | x x x _ _ _ _ _ |
i = 2 | x x x x _ _ _ _ |
i = 3 | x x x x x _ _ _ N
i = 4 | x x x x x x _ _ |
i = 5 | x x x x x x x _ |
i = 6 | x x x x x x x x _
|-----N + 1-----|
The area of the whole rectangle is ~ N * N ( actually N * (N + 1), but it does not matter that much here), so we see that there ~ N ^ 2 / 2 operations. And it's O(N^2).