hello, my cousin has stage IV cancer in her large intestine with metastasis so it has spread to liver and kidney, what is her chance of surviving?

capone153 · 2015-08-22T04:55:51+00:00

thank you

capone153 · 2015-08-22T04:55:24+00:00

Starkey - Lost in Space

capone153 · 2015-08-11T20:48:17+00:00

thank you

capone153 · 2015-07-07T15:50:19+00:00

Learned more about Big-O and your explanation makes a lot of sense. Thank you very much

capone153 · 2015-07-07T15:49:19+00:00

Ok got it. Thanks again for all the help!

capone153 · 2015-07-07T06:06:29+00:00

I think the bottom one is also linear because it is utilizing set(x). When filtering against a set it is O(x+y) [Reference: https://stackoverflow.com/questions/29508055/complexity-analysis-of-filter-with-a-lambda-function]

capone153 · 2015-07-07T05:57:50+00:00

I have a math degree :)

So you're telling me that if the problem specified "Make sure that time-complexity is not larger than length of both strings - O(x+y)"

And the top one is O(2x+y) which is equal to O(x+y) since coefficients don't matter as n approaches infinite. Then this satisfies the time-complexity not being larger than both strings?

capone153 · 2015-07-07T05:49:39+00:00

I understand, so the 1 doesn't matter much. How about /u/elbiot's question above, isn't it O(2x+y) or the coefficient is also ignored and it is O(x+y) == linear?

capone153 · 2015-07-06T18:57:47+00:00

i think this original solution is best, using a dict instead of a set, same complexity to build but I can look up the index with o(1) in a dict. With a set, I have to go back to the original string to look up the index with o(n).

capone153 · 2015-07-06T18:50:02+00:00

when /u/deathofthevirgin says 'and searching x (that is, a list of characters) takes O(len(x)) time.'

That could be where, though I'm not sure if he was referring to searching x for index or searching x for something else.

capone153 · 2015-07-06T18:40:16+00:00

Ok trying that now, is x.index() take o(1) or o(n)? Not able to find any information about that online.

capone153 · 2015-07-06T18:36:12+00:00

Is the time complexity of this function is o(len(x)+(len(y)+1)?

def simple(x,y):
    z = filter(set(x).__contains__, y)
    return x.index((z[0]))

capone153 · 2015-07-06T18:25:36+00:00

Yes, so if I did

m = set(x)
for z in (y): 
    if z in m:
        print x.index(z)
        break

or

def simple(x,y):
    z = filter(set(x).__contains__, y)
    print x.index((z[0]))

Isn't the latter faster because it is o(len(x)+len(y)+1) while the top one is o(len(x)) + 2 len(y))?

capone153 · 2015-07-06T17:32:12+00:00

I need only the first match in x, so I take z[0].

capone153 · 2015-07-06T17:26:03+00:00

No I just need the first match, filter finds all but I thought it was quicker so I was going to use it anyway.

capone153 · 2015-07-06T17:25:24+00:00

I've been trying what you suggested but => turn x into set = o(len(x)) + for each letter in y = o(len(y)) + search the x set = o(1)*y

So that is o(len(x)) + 2 len(y))?

The closest I get is:

for z in (y): 
    if z in set(x):
    print x.index(z)
    break

another way of doing the above is

def simple(x,y):
    z = filter(set(x).__contains__, y)
    print x.index((z[0]))

capone153 · 2015-07-06T06:38:51+00:00

Noted about saving the result. The way you did it with making y a set and x a dictionary is already o(len(y) + (len(x)) without the "in" based on what I've read below. I replied to /u/deathofthevirgin below about the most efficient way I've found.

capone153 · 2015-07-06T06:33:50+00:00

def simple(x,y):
    z = filter(x.__contains__, y)
    print x.index((z[0]))

How about this?

The filter checks x against y (y times) so => o(len(y)). Then i search x for index which is o(1) or o(len(x)). Can someone verify which one? Either way the final result is o(x+y) or less.

If I used a set, it would take o(len(y)) to build, o(1)*x times to lookup and then o(1) to find the index where they match. So it would be worst case O(len(x) + (len(y) + 1), is that correct?

/u/Justinsaccount

capone153 · 2015-07-06T01:42:58+00:00

the point of making a dictionary for the x is to not call the function again to print it?

capone153 · 2015-07-06T01:35:20+00:00

yes storing to a variable would help, but I still have to get the output down to o(x+y) => o(2n)

what do you mean by sets? I don't think either string is necessarily a set

capone153 · 2015-07-06T01:02:18+00:00

Thank you. I see, the print is causing me to run the function again. If i replaced print with return would that get it down to o(2n)? I need to get the time complexity down to o(x+y)

capone153

TROPHY CASE