问题描述:

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).

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.