Project Euler #14: Longest Collatz sequence
Your algorithm involves the following:


Make a list of size 1,000,000
Until done:
a. Make a new list of size 1,000,000
b. Make  another new list of size 1,000,000
c. Make another new list of size 1,000,000
d. Iterate over it twice
e. And then another time


That strikes me as extremely expensive to start out. Furthermore, consider all the extra work we're doing. The sequence in the problem example is:

13 --&gt; 40 --&gt; 20 --&gt; 10 --&gt; 5 --&gt; 16 --&gt; 8 --&gt; 4 --&gt; 2 --&gt; 1


You are calculating all 10 of those chains independently. That means you're calculating the chain for 16 six times. That's an enormous amount of extra work. The actual longest chain is of length 525. That means that for the actual answer, we are doing 524 more iterations than necessary, and we end up having to create over 1500 lists of size one million. Even if most of the time, most of our elements will be 0! We can do way better by just memoizing, which also takes less memory to boot! 

Just looking at some runtimes for small values of target (10x each via timeit):

target        OP
100        0.09s
1000       1.29s
10000     19.07s


A few code comments before I get into a simpler algorithm. Don't use map(). It's far more complicated than a list comprehension. These two:

first_list = list(map(lambda x : x , range(1,target+1)))
new_list = list(map(lambda x : x/2 if x%2==0  else 3*x+1 , given_list))


Can be replaced by:

first_list = range(1, target+1)
new_list = [x/2 if x%2 == 0 else 3*x+1 for x in given_list]


The latter could be wrapped further to avoid the extra list comprehension just to move your 1s to 0s but it's overkill anyway. Similarly, your:

reduce(lambda x,y : x+y, new_list)


Could be replaced by:

sum(new_list)


Better Algorithm

First, let's start with our handy memoize decorator:

def memoize(f):
    cache = {}
    def wrapper(*args):
        if not args in cache:
            cache[args] = f(*args)
        return cache[args]
    return wrapper


And then start separating our concerns. We will write a function that for ONE value of n finds the length of a chain:

@memoize
def collatz_chain(n):
    if n == 1:
        return 1
    elif n % 2 == 0:
        return 1 + collatz_chain(n/2)
    else:
        return 1 + collatz_chain(3*n+1)


And then we just need to wrap all of that:

return max(range(1, target+1), key=collatz_chain)


It's still linear time, but I end up doing FAR less work than you have to, since most of the time I'm doing almost nothing. And the numbers show it:

target        OP    memoize
100        0.09s     0.003s   ~30x
1000       1.29s     0.024s   ~54x
10000     19.07s     0.239s   ~80x