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'.
length = len(s)
last = len(s)-1
count = 0
for index, i in enumerate(s):
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
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
count += 1
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).
Well, lets consider this. The size of the input is
n = len(s). For each character, you loop from 0 to index. So we can get the following
for i = 0 to n for j = 0 to i + 1 1
Which can be reduced to
for i = 0 to n (i + 1)(i + 2)
Which then gives us
for i = 0 to n i^2 + 3i + 2
We can then split this up and reduce it, we know that
3i + 2 will reduce to
3(n)(n + 1) + 2n = 3n^2 + 5n which right away is not linear as it's O(n^2).
I also don't understand what you're doing by having the second for loop, you can compute a palindrome in linear time by comparing the last and first characters.
If you're wondering how: http://rosettacode.org/wiki/Palindrome_detection#Python
This is not O(N) time. Although you loop through the
enumerate(s) array just once. During every loop you do some extra work. Let us assume the length of the array is N. So the total number of repetitions is going to be approximately 1+2+3+..+N which is N*(N+1)/2 which simplifies to an O(N^2) running time.