Is the complexity of this code \$O(n^3)$? How can I improve the efficiency and reduce the complexity?

A = [3,2,4,2,4,2,4,5,3]
n= len(A)
def ALG2 (A,i,j):  #to check whether all entries between A[i] and A[j] are the same
    if i==j:
        return True     
    for k in range (i,j-1):
        if A[k] != A[k+1]:  
            return False
    return True

def  ALG1(A,n):   #find the max length of the arrays that are found in ALG2 
    for i in range (0,n-1):
        for j in range (i+1,n-1):    
            if ALG2(A,i,j) and (j-i)>l:
                l= j-i

    return l

result = ALG1(A,n)

print (result)
  • 2
    \$\begingroup\$ I'm not sure why this has a down vote :( Could you add a little more description on what this code is doing? If this is a programing challenge including the challenge description and a link would be all that's needed! \$\endgroup\$
    – Peilonrayz
    Feb 15, 2019 at 21:17
  • \$\begingroup\$ Yes, I believe if you have a loop in a function being called inside of a loop you must also add that as a nested loop. \$\endgroup\$ Feb 15, 2019 at 21:38
  • \$\begingroup\$ Welcome to Code Review! I changed the title so that it describes what the code does per site goals: "State what your code does in your title, not your main concerns about it.". Feel free to edit and give it a different title if there is something more appropriate. \$\endgroup\$ Feb 15, 2019 at 21:55
  • \$\begingroup\$ It is not a challenge. It is my assignment actually . It is my first day to use stackexchange. really sorry for causing any inconvenience \$\endgroup\$
    – Wing Ho Lo
    Feb 15, 2019 at 23:01
  • \$\begingroup\$ What is the expected result for A = [3,2,4,2,4,2,4,5,3]? \$\endgroup\$
    – vnp
    Feb 16, 2019 at 0:50

2 Answers 2

  1. You should use better function names ALG1 and ALG2 don't really say what they're performing.
  2. You should keep the creation of A, n and result at the bottom of your code.
  3. You should keep your 'main' code in a main guard block:

    if __name__ == '__main__':
        A = [3,2,4,2,4,2,4,5,3]
        n= len(A)
        result = ALG1(A,n)
  4. You should follow PEP 8, so that it's easier for others to read your code.

  5. ALG2 can be simplified by slicing the array from i to j, A[i:j], and then checking if the set has a size of one.

    def ALG2(A, i, j):
        return len(set(a[i:j])) == 1
  6. Your entire code can be drastically simplified by using itertools.groupby.

    import itertools
    def ALG1(array):
        sizes = (
            sum(1 for _ in g)
            for _, g in itertools.groupby(array)
        return max(sizes, default=0)
  • \$\begingroup\$ wow so is the itertools installed in python? and what is the itertools really for? \$\endgroup\$
    – Wing Ho Lo
    Feb 16, 2019 at 17:05
  • \$\begingroup\$ @WingHoLo Yes it's installed with Python. It's a collection of functions to help with iterators. \$\endgroup\$
    – Peilonrayz
    Feb 16, 2019 at 17:08

Your algorithm is indeed n^3, but you can do it in linear time. https://ideone.com/Ke3q5o

A = [3,2,5,4,4,4,4,2,4,4]

def findLongestContinuousSection(A):
    if len(A) == 0:
    longestStart = 0
    longestStop = 0
    longestLength = 0
    longestVal = 0
    curStart = 0
    curStop = 0
    curLength = 1
    curVal = A[0]
    for k in range(1,len(A)-1):
        if curVal != A[k]: # record cur as longest
            longestVal = curVal
            longestStart = curStart
            longestStop = curStop
            longestLength = curLength
            curStart = k
            curStop = k
            curLength = 1
            curVal = A[k]
        else: # continue to build current streak
            curStop = k
            curLength += 1
    return (longestStart, longestStop, longestLength, longestVal)

print findLongestContinuousSection(A)
  • \$\begingroup\$ I'm confused where the Code Review is. Also this code looks needlessly long. \$\endgroup\$
    – Peilonrayz
    Feb 16, 2019 at 11:56
  • \$\begingroup\$ I only focused on the complexity. \$\endgroup\$ Feb 16, 2019 at 12:57
  • \$\begingroup\$ so here we return 4 elements in a function. But it cannot be done in python or any programming at all right? \$\endgroup\$
    – Wing Ho Lo
    Feb 16, 2019 at 17:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.