I've been told the below code is = O(MN) however, I come up with O(N^2). Which is the correct answer and why?

My thought process: nested for loops plus if statements --> (O(N^2)+O(1)) + (O(N^2)+O(1)) = O(N^2)

Thank you

```
public static void zeroOut(int[][] matrix) {
int[] row = new int[matrix.length];
int[] column = new int[matrix[0].length];
// Store the row and column index with value 0
for (int i = 0; i < matrix.length; i++)
{
for (int j = 0; j < matrix[0].length;j++) {
if (matrix[i][j] == 0)
{
row[i] = 1;
column[j] = 1;
}
}
}
// Set arr[i][j] to 0 if either row i or column j has a 0
for (int i = 0; i < matrix.length; i++)
{
for (int j = 0; j < matrix[0].length; j++)
{
if ((row[i] == 1 || column[j] == 1)){
matrix[i][j] = 0;
}
}
}
}
```

What does M and N refers to? My assumption is that it refers to "rows" and "columns" respectively. If it is so, then the equation is O(MN) because you loop through M number of N times.

O(N^2) will be correct IF rows and columns are equal.

Similar Questions

I'm really confused about the differences between big O, big Omega, and big Theta notation. I understand that big O is the upper bound and big Omega is the lower bound, but what exactly does big Theta

So I have a loop embedded inside a loop here: int a,b,n; for (a = 1; a <=n; a++) { for (b = 0; b < n; b+=a) cout << hey << endl; } n is a power of 2 I'm trying to understand how t

find the big oh characterization input: n s<-0 for i<-1 to n^2 do for j<-1 to i do s<-s+i Both loops iterate n^2 times. I'm not sure if I should add or multiply the loops. Right now I thi

If I understand Big O Notation, and believe me my understanding at this point is probably much lower than most, the following line of code is O(n2) per the comment by Keyser this is in fact already

The question is rather simple, but I just can't find a good enough answer. On the most upvoted SO question regarding the big-O notation, it says that: For example, sorting algorithms are typically co

I'm reading a textbook right now for my Java III class. We're reading about Big-Oh and I'm a little confused by its formal definition. Formal Definition: A function f(n) is of order at most g(n) - th

What Big-O notation questions have you been asked? Did you find them to be good questions? Did the interviewer actually understand the concept?

My understanding is that if an algorithm is O(1) it is also O(n), O(n^2), O(n^3) and so on which makes it seem useless. For example, if someone asked me for the Big-Oh notation of any algorithm, I cou

This question looks simple to me, but just wanted to see whether i am moving in the right direction. Is it as simple as saying when n =1 ??

using regular expression in R, an example of data below: word <-c(Look at this and say: Oh ya, , Oh thanks!, what?! Oh my god!, oh, No!, What's that for?, Don't you see that? oh you don'

In Big Theta notation, do the constants c1 and c2 differ for each value of n?. Definition: Theta(g(n)) = {f(n): there exist c1 >= 0, c2 > 0 and n0 > 0 such that for all n >= n0, 0 <= c1

What are the differences between the notation: some text #{some_ruby_code} some text #{some_more_ruby_code} some_other_text and ERB.new( some text <%=some_ruby_code%> some text <%=some_

I'm getting objects containing big numbers from a web service and show them in an <input type=number> field. It works until angular begins to show the values in scientific notation. The value

For large problems sizes, an algorithm with time cost O(2^n) is faster than an algorithm that has time cost O(N^2) Is this true or false? What I think is that if C^n, C = constant and C > 1, then

Is it common that a higher value for Big-O notation is used for convenience or simpler looks? For example: I'm looking at this algorithm bifragment gap carving shortly explained here (page 66). If I

void foo(float[] array, int start, int end){ if((end-start) <=1) return; int x = (end-start) / 5; int y = 2*x; int z = 4*x; foo(array,start,start+y); for(index = y; index < z; index++){ array[in

Give the smallest O() estimate you can for the following functions: 4n2 + 5n – 8 = O(...) log(n)2 + n = O(...) If you guys can, explain the answer rather than giving it to me. A question like this wi

What Big-O notation would this fall under? I know setSearch() and removeAt() are of order O(n) (assume they are either way). I know without the for loop it'd be O(n), for certain, but I get confused h

How can I convert this query into dot notation var x = from Prods n in Cat.Prod.GetAllProds() orderby n.Name select new { Name = n.Name, Cost = n.Cost };

For example, if time complexity of merge sort is O(n log n) then why it is big O not theta or omega. I know the definition of these, but what I do not understand is how to determine the notation based

Its a exercise that ask to indicate the class Big-Theta(g(n)) the functions belongs to and to prove the assertion. In this case f(n) = (n^2+1)^10 By definition f(n) E Big-Theta(g(n)) <=> c1*g(n)

This question already has an answer here: Confused about the time complexity of nested loops and looking for tips 1 answer So I understand that if the two while loops were just while (x < n)

In most popular languages like C/C++/C#/Erlang/Java we have threads/processes; there is GPGPU computation market growing. If algorithm requires N data independent steps we get not the same performance

I've just read an article about a breakthrough on matrix multiplication; an algorithm that is O(n^2.373). But I guess matrix multiplication is something that can be parallelized. So, if we ever start

I am in the process of learning about big oh notation. For the code below, I have a program that counts the number of words, skipping over the delimiters. For this algorithm, the for loop would be for

I had a test about asymptotic notations and there was a question: Consider the following: O(o(f(n)) = o(f(n)) Write in words the meaning of the statement, using conventions from asymptotic notation

Some standard books on Algorithms produce this: 0 ≤ f(n) ≤ c⋅g(n) for all n > n0 While defining big-O, can anyone explain to me what this means, using a strong example which can help me to visual

This question already has an answer here: Explain Python's slice notation 19 answers Why is this list slice treating 0 and 1 as the same in Python? [duplicate] 2 answers Let me preface this

I have gone through the N2 CMS documentation at length and can see no obvious set of steps to accomplish this. The task is to create a new Web Forms CMS app based on N2. Basically to take the Stripes

if T(n) is O(n), then it is also correct to say T(n) is O(n2) ?

For the following code: print a for (i = 0; i < n; i++) for (j = i; j < n; j++) print b Obviously, the big oh of n for print a is just 1, but I don't understand how the second part is 1/2n + 1

I'm creating a Form and adding a checkbox with ZF2, but for some reason the options dont get sent when I use array notation. So this: class PageForm extends Form { public function __construct($name =

I had a question about Big O vs little o notation. It seems intuitively, that Big O is like <= while little o is like <. Does that mean that if something is little o of f(n), it is also Big O of

I was just reading another question and this code intrigued me: for(i = 0; i < n; i++) { for(j = 0; j < i*i; j++) { for(k = 0; k < i*j; k++) { pseudo_inner_count++; for(l = 0; l < 10; l++)

I wonder if there's any tool/website where I can plot some run times as graphs. Because, the asymptomatic notation is often not what I wanted i.e. Don't want to ignore constants. For example, suppose

When one byte is represented by 8 bits in binary notation you have a sequence of 8 possible 1's and 0's. So 00101010 can be shortened to 2A using hexadecimal notation. My book says you can shorten tha

while (n >= 1) n /= 2; I am unable to get the Big-O notation for this

I am trying to understand what exactly Big O notation is. I understand it in the literal and practical sense by going through the answers of similar questions in SO. But what the answers don't explain

Possible Duplicate: What is the difference between Θ(n) and O(n)? It seems to me like when people talk about algorithm complexity informally, they talk about big-oh. But in formal situations, I ofte

Given the following example: library(data.table) mat <- data.table(x = c(1:10), y = c(11:20), z = c(21:30)) cut.head <- c(0, 2, 1) cut.tail <- c(3, 1, 2) cut.head represents the number of ro

I'm building a simple c++ platform for a yu-gi-oh duel but I found a problem with card effects. Since almost every card has a different effect this means that I have to write a different function ever

I've been using N2 cms for a couple of projects using some parts from their templates project but haven't come across a solid blogging component. Basically looking for something pretty simple that doe

I assume that a particular example in my book is wrong. But am I correct? Example: 3log n + 2 is O(log n) Justification: 3log n + 2 <= 5 log n, for n>=2. I understand how they get the c=5 (sinc

I want to format a floating point value to n significant digits but never using scientific notation (even if it would be shorter). The format specification %f doesn't deal in significant digits, and %

def filter(f, lst): if lst == []: return [] if f(lst[0]): return [lst[0]] + filter(f, lst[1:]) return filter(f, lst[1:]) def my_reverse(lst): # Reverse the list def reverse_helper(x,y): if x == []: re

Possible Duplicate: Big Theta Notation - what exactly does big Theta represent? I understand it in theory, I guess, but what I'm having trouble grasping is the application of the three. In school, w

Karatsuba Algorithm involves the recursion relation T(n) = 3T(n/2) + n. By the recursion tree method, we can approximate the big O of T to be O(nlog23) However, by the substitution method I am having

Can an arbitrary number of ContentItems of the same class to be added to a page in N2? And can they be nested? I.e. Is there a way to define a collection of ContentItems as a property in N2? I’d also

I know there are quite a bunch of questions about big O notation, I have already checked Plain english explanation of Big O , Big O, how do you calculate/approximate it?, and Big O Notation Homework--

I came upon a notation I'm not too familiar with and would like some direction to where to look. the notation is selector event : function() {} so for example .elementClass change : function() {}