Question

What is the computational complexity of the following Python code? http://ideone.com/mGBQu

Answer 1

what it does

Answer 2

it's a puzzle, find out :-D

Answer 3

I'm sure ffm would know right away.

Answer 4

idk whats lambda

Answer 5

lambda <parameters> = expression

is just syntactic sugar for

def identifier(parameters):
return expression

only difference is that there does not need to be an identifier.

Answer 6

so lambda expressions in Python are simply anonymous functions

Answer 7

and I think they're coming to Java :-D

Answer 8

so you can write messy code just like I did :-D

Answer 9

oops it's lambda <parameters>: expression

and if you want to use an identifier, then you write

identifier = lambda <parameters>: expression

and call it just like you would call a normal function

Answer 10

they can be used in conjunction with the higher order functions like map, reduce, filter etc.

for example, reduce(lambda x,y: x+y, map(lambda x: x*x, range(1, 1001))) returns the sum of the squares of every number in the range [1, 1000]

Answer 11

Here's a hint: http://rosettacode.org/wiki/Python

Answer 12

Another hint: http://ideone.com/7vIFn

Answer 13

I will guess that the running time is in O(n^2), and maybe \[\Omega(1)\]where n is the size of the list passed to ss, and the best-case is when n = 1.

Answer 14

(assuming lambda calls take constant time)

Answer 15

right @ bmp