CODEWITHSUNDEEP
pythonarraysfor-loopmatrix
Pazio
Pazio

Reputation: 11

How to iterate through a Matrix without 2 for-loops

I have an exercize that demands an iteration through the elements of a matrix 'm', the difficulty is that the running time is supposed to be linear, meaning that if I use forloops, only one is allowed.

My Problem is now, that I always find myself wanting to use 2 forloops, but the running time wouldn't be linear, it would be quadratic. I was thinking about just iterating through m[i] and then checking if these are only the Int 0, but that would be 2 forloops again or maybe see if I could join the elements. Sadly, I couldn't find anything helpful already. I also thought about using the 'x in list' argument, but that wouldn't be helpful either.

Thanks in advance. 

m = [[0,0,0],
     [1,0,1],
     [1,0,0]]


#for i in m
#check all elements in m[i] for Ints '0'    

#m[0] --> All Elements are the Integer 0
#--> Output: True.
#The output should be a Boolean 'True', when the elements of one m[i] are all Integers 0.

Upvotes: 1

Views: 1691

Answers (1)

peels
peels

Reputation: 91

I would keep in mind that run-time analysis is based on the size of input. That is, if your input consists of n elements and you iterate over each element exactly once, this is O(n). If your matrix is size n x m, then I believe linearity would be defined as O(n x m), i.e. linear in the size of the input.

Also, the presence of a nested for loop does not necessarily mean that a program's runtime is quadratic, though this can be a helpful way to think about runtime.

EDIT: This doesn't change the theoretical runtime, but you can look into vectorized built-in functions (like sum in python) to handle each row altogether. As I said, this does not change the algorithmic runtime, but under-the-hood optimizations and vectorization can bring a speed up over a simple iteration over each matrix element.

As an elaboration to the "two for loops always means O(n^2)": this is only true in situations like: 

# n elements in the input
for i in range(n):
    for j in range(n):
        # do things

# another possibility
# n elements in the input
for i in range(n):
    for j in range(i):
        # worst case, i == j, bringing this to O(n^2)
        # do things

Upvotes: 1

Related Questions