11 Replies - 1921 Views - Last Post: 23 July 2014 - 01:19 PM

#1 code_m  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 24
  • View blog
  • Posts: 202
  • Joined: 21-April 09

Codility Challenge: Detected Time Complexity

Posted 20 July 2014 - 08:12 PM

I'm trying to prep for an interview tomorrow, so I was doing some coding challenges for fun. I have a love/hate relationship with Codility, namely do to the fact that the tests they run your code through isn't 100% clear before submitting your solution.

Anyway, to the point. I was doing the Tie Ropes challenge. It took many tries simply because I was reading too fast and I was trying to solve it the pythonic way. The challenge was looking for O(n) complexity.

My problem is that my best pythonic solution was rated at O(n**2):
def solution(K, A):
    start = 0
    end = 1
    count = 0
    while end <= len(A):
        while end <= len(A) and sum(A[start:end]) < K:
            end += 1
        if sum(A[start:end]) >= K:
            count += 1
        start = end
        end += 1
    return count


To me it looks like O(n) complexity since the loop(s) iterate with end of the slice, and regardless of which loop you are in it increments the end element. (Apologies to those unfamiliar with a Python slice. Practically all other languages you'd need a "start" and "length" instead.)

What says you on this snippet? O(n) or O(n**2)? Explain please.

Is This A Good Question/Topic? 1
  • +

Replies To: Codility Challenge: Detected Time Complexity

#2 sepp2k  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2112
  • View blog
  • Posts: 3,230
  • Joined: 21-June 11

Re: Codility Challenge: Detected Time Complexity

Posted 20 July 2014 - 08:24 PM

sum(A[start:end]) takes O(end - start) time, which is O(end) in the worst case (that is the case where start stays at zero until the end). It will be executed with end taking the values 1 through n. So in total the time complexity will be O(sum end = 1 .. n: n) = O(n^2).
Was This Post Helpful? 4
  • +
  • -

#3 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10558
  • View blog
  • Posts: 39,065
  • Joined: 27-December 08

Re: Codility Challenge: Detected Time Complexity

Posted 20 July 2014 - 08:33 PM

Rather than using the built-in sum() function, use a sum variable. Add the first n elements from start until end. If that is less than K, look at the end + 1 element and add it to the running total. Then look at the end + 2 element and add it to the running total if necessary. This is a linear time complexity solution.
Was This Post Helpful? 1
  • +
  • -

#4 code_m  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 24
  • View blog
  • Posts: 202
  • Joined: 21-April 09

Re: Codility Challenge: Detected Time Complexity

Posted 20 July 2014 - 08:41 PM

View Postsepp2k, on 20 July 2014 - 11:24 PM, said:

sum(A[start:end]) takes O(end - start) time, which is O(end) in the worst case (that is the case where start stays at zero until the end). It will be executed with end taking the values 1 through n. So in total the time complexity will be O(sum end = 1 .. n: n) = O(n^2).

Thanks. Didn't think that the sum's complexity would change the algorithm complexity.

View Postmacosxnerd101, on 20 July 2014 - 11:33 PM, said:

Rather than using the built-in sum() function, use a sum variable. Add the first n elements from start until end. If that is less than K, look at the end + 1 element and add it to the running total. Then look at the end + 2 element and add it to the running total if necessary. This is a linear time complexity solution.

I figured that out. I was bothered by the reported complexity, not the actual solution. That's why it's in the Computer Science forum, not the "programming help" forum for python.
Was This Post Helpful? 1
  • +
  • -

#5 Skydiver  Icon User is online

  • Code herder
  • member icon

Reputation: 3567
  • View blog
  • Posts: 11,086
  • Joined: 05-May 12

Re: Codility Challenge: Detected Time Complexity

Posted 20 July 2014 - 09:06 PM

View Postcode_m, on 20 July 2014 - 11:41 PM, said:

View Postsepp2k, on 20 July 2014 - 11:24 PM, said:

sum(A[start:end]) takes O(end - start) time, which is O(end) in the worst case (that is the case where start stays at zero until the end). It will be executed with end taking the values 1 through n. So in total the time complexity will be O(sum end = 1 .. n: n) = O(n^2).

Thanks. Didn't think that the sum's complexity would change the algorithm complexity.


I wasn't expecting this as well. I was under the impression that when a hypothetical algorithm was presented, we were only supposed to analyze what was in the thing that was presented and not dig deeper into how any utility functions may work.

For example if I had the following:
product_of_matrices = identity_matrix;
for (int i = 0; i < N; i++)
    product_of_matrices = product_of_matrices * matrix[i];



Is this an O(n) algorithm, or is it at best O(n^2.xxx) because of the minimum complexity for matrix multiplication?
Was This Post Helpful? 0
  • +
  • -

#6 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10558
  • View blog
  • Posts: 39,065
  • Joined: 27-December 08

Re: Codility Challenge: Detected Time Complexity

Posted 20 July 2014 - 09:17 PM

In the case of algorithm analysis, one might make an assumption of such an operator taking O(1) time. Unless such an assumption was made, then your algorithm would be O(n2.xxxx).
Was This Post Helpful? 1
  • +
  • -

#7 code_m  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 24
  • View blog
  • Posts: 202
  • Joined: 21-April 09

Re: Codility Challenge: Detected Time Complexity

Posted 21 July 2014 - 06:38 AM

View Postsepp2k, on 20 July 2014 - 11:24 PM, said:

sum(A[start:end]) takes O(end - start) time, which is O(end) in the worst case (that is the case where start stays at zero until the end). It will be executed with end taking the values 1 through n. So in total the time complexity will be O(sum end = 1 .. n: n) = O(n^2).


So I still wanted to prove this, so I refactored the code to use only one loop, but still operate using sum and a slice. This did improve the overall performance, but was still rated at O(n**2):
def solution(K, A):
    start = 0
    count = 0
    for end in xrange(1, len(A) + 1):
        if sum(A[start:end]) >= K:
            start = end
            count += 1
    return count


So it seems this is definitely the case. Manually calculating the sum does provide a O(n) solution, though I don't really care for it.
Was This Post Helpful? 1
  • +
  • -

#8 sepp2k  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2112
  • View blog
  • Posts: 3,230
  • Joined: 21-June 11

Re: Codility Challenge: Detected Time Complexity

Posted 21 July 2014 - 07:41 AM

View PostSkydiver, on 21 July 2014 - 06:06 AM, said:

I wasn't expecting this as well. I was under the impression that when a hypothetical algorithm was presented, we were only supposed to analyze what was in the thing that was presented and not dig deeper into how any utility functions may work.


First of all this wasn't a hypothetical algorithm, but a real piece of code. Since the complexity was determined programmatically (presumably by measuring the time taken for various input sizes and checking which common functions it matched), it wouldn't even be possible to distinguish between "the thing presented" and the utility functions.

That said even if we were talking about theory, I would find it very strange to assume that any utility functions are assumed to be O(1). It may often make sense to assume that certain operations are O(1) if they're not relevant to what we really want to talk about. For example in a sorting algorithm we often assume that comparisons are O(1) even though that may often not be the case in practice (say, when we're sorting a list of strings). But I'd hardly say it makes sense to assume such things as a general rule.

As an example take this algorithm to check a given list for duplicates:

sort(lst)
for i in range(0, len(lst) - 1):
  if lst[i] == lst[i+1]:
    return true

return false



Everything after the sort is O(n), but the whole thing is still O(n log n). We wouldn't claim that this algorithm can detect duplicates in unsorted lists in O(n) time just because sort is a built-in function and therefore does not count.

PS: In your example the complexity would depend on the size of the matrices. Generally the complexity would be O(N * M**2.xxx) where N is the number of matrices and M is the size of each matrix. If we assume the matrix size to be constant (because they will be in our use case or just because we're more interested in how the algorithm behaves with more matrices than in how it behaves with bigger ones), the algorithm becomes O(N). However this has nothing to do with matrix multiplication being a utility function, but rather with the fact that the complexity of each matrix multiplication does not depend on the number of matrices in our list.

This post has been edited by sepp2k: 21 July 2014 - 07:53 AM

Was This Post Helpful? 2
  • +
  • -

#9 cfoley  Icon User is offline

  • Cabbage
  • member icon

Reputation: 1985
  • View blog
  • Posts: 4,119
  • Joined: 11-December 07

Re: Codility Challenge: Detected Time Complexity

Posted 21 July 2014 - 02:50 PM

I would really like to know what makes your first solution "pythonic". I don't understand the term. Another one I see that I don't understand is "the ruby way".

Here is my attempt. Is it pythonic?

def solution(K, A):
    result = 0
    currentLength = 0
    for x in A:
        currentLength += x
        if (currentLength >= K):
            result += 1
            currentLength = 0
    return result
        

Was This Post Helpful? 0
  • +
  • -

#10 Skydiver  Icon User is online

  • Code herder
  • member icon

Reputation: 3567
  • View blog
  • Posts: 11,086
  • Joined: 05-May 12

Re: Codility Challenge: Detected Time Complexity

Posted 23 July 2014 - 05:42 AM

I'm not a Pythonista, but based on the Zen of Python, it looks like you hit the "Simple is better than complex." aspect right on the head.
Was This Post Helpful? 1
  • +
  • -

#11 iCode113  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 3
  • Joined: 23-July 14

Re: Codility Challenge: Detected Time Complexity

Posted 23 July 2014 - 12:39 PM

In my understanding(simplified) any algorithm that has a loop inside a loop and both depend on n it will automatically have at the least an O(n**2) complexity
Was This Post Helpful? 0
  • +
  • -

#12 sepp2k  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 2112
  • View blog
  • Posts: 3,230
  • Joined: 21-June 11

Re: Codility Challenge: Detected Time Complexity

Posted 23 July 2014 - 01:19 PM

View PostiCode113, on 23 July 2014 - 09:39 PM, said:

In my understanding(simplified) any algorithm that has a loop inside a loop and both depend on n it will automatically have at the least an O(n**2) complexity


That's not true. In the OP's code both the inner loop and the outer loop increment the same counter variable, which is never reset to 0. So regardless of how many loops there are, it is clear that the counter will only be incremented n times before the loop terminates. Therefore it would be O(n) if everything inside the loop were O(1).

Another counter example would be this code:

for(int x = 1; x <= n; x *= 2) {
  for(int y = 1; y <= n; y *= 2) {
    // do something in O(1) time
  }
}



Here the outer loop executes log n times and each time the inner loop also executes log n time. The contents of the inner loop are O(1), so despite having two nested loops both depending on n, the total time complexity is O(log˛ n), which is a lot less than O(n^2) or even O(n).
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1