Determine time and space complexity of the following ,and express it using Big Oh notation:
Procedure Add(a,b,c,m,n)
{ // a,b and c are 2-dimentional arrays of size m X n
for i=1....m do
for j=1....n do
c[i,j]=a[i,j]+b[i,j];
}
I want any one to answer and explan the question please
I think the answer to time complexity is :
nm+n+m+2
but I can't give the Big Oh for it .
Tarek: have you done a course on this subject? Did you go to classes? Did you get any notes? Have you tried a search for "time and space complexities"? Have you thought about this question? Have you asked yourself why you are studying if you can't be bothered to do any of the learning?
I think the answer to time complexity is :
nm+n+m+2but I can't give the Big Oh for it .
Don't worry about the other poster.
Your answer for the time complexity is generally correct. The question is, do you know what Big O notation really means?
It is used to compare growth rates between functions. Hopefully, you know what it means for one function to grow faster than another. If a function f grows slower than or equal to a function g defined by g(x) = x^2, we would say that f is in O(x^2). For example, if f(x) = 3x^2, then their growth rates are equal, hence O(x^2) is an upper bound for f. O(x^3) would be another valid upper bound, since 3x^2 grows slower than x^3. But saying O(x^2) is tighter and more informative.
You have found a correct formula for the running time of your algorithm. If you wanted, a cheapo growth bound for your algorithm could be O(nm+n+m+2). Your function certainly grows at the same rate as or slower than itself. But it can be shown using some math that f(x,y) = xy grows at the same rate as xy+x+y+2, so the growth bound of O(nm) works, too.
Formally, big-O notation represents sets of functions -- the set of all functions that grow slower than or equal to the contained expression (using a certain definition of "slower than or equal to"). For example, O(n^2) is a set of functions that includes functions like f(n) = n + 3, g(n) = 3n^2 + 5n + 7, h(n) = log n + n + n log n, and so on.
If you don't understand why 3n^2 + 5n + 7 is said to grow at the same rate as n^2, say so and I'll explain it to you completely. The above explanation of big O notation is kind of quick and might be insufficient.
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.