## Narue 5,707

>Can you describe an algorithm that is O(nm)?
>I'm guessing it would be something like traversing a two-dimensional array.

Good guess. That's an excellent way of describing O(nm).

>The two loops needed to do that is throwing me off however.
>It's making me think that it could be O(n^2).

If it helps, you can think of O(n^2) as O(nn), redundant as it may be. The difference here is that with O(nm), n and m don't have to be the same value. They can be, and in that case the time complexity is indeed quadratic.

## ecliptikz

>The two loops needed to do that is throwing me off however.
>It's making me think that it could be O(n^2).

If it helps, you can think of O(n^2) as O(nn), redundant as it may be. The difference here is that with O(nm), n and m don't have to be the same value. They can be, and in that case the time complexity is indeed quadratic.

Thanks! Good way to put it. I can see it being quadratic if the matrix contains the same amount for each dimension.

...

## mridul_018

Given a 2D array which is sorted in non-decreasing order(increasing). what will be the expected time complexity to find an element in that 2D array?

## Rashakil Fol 978

Gee, why don't you figure this out for yourself?

## Cowst

Picking up from the 2D array SEARCH (not sorting), and assuming it to be n * n.
Just want to check if I got it right (intuitively):
- the worst case is O(n^2) - potentially last entry
- best case is O(1) - potentially first entry
- average case? if I should imagine an average, I would expect the searches to be distributed in the middle, so n/2 * n/2, which would be still O(n^2)

Is this correct?

## Cowst

Sorry, I cannot find an EDIT button...

What I meant was: from 2 posts before "Given a 2D array which is sorted in non-decreasing order(increasing). what will be the expected time complexity to find an element in that 2D array?"
Therefore my question quoted here:

Picking up from the 2D array SEARCH (not sorting), and assuming it to be n * n.
Just want to check if I got it right (intuitively):
- the worst case is O(n^2) - potentially last entry
- best case is O(1) - potentially first entry
- average case? if I should imagine an average, I would expect the searches to be distributed in the middle, so n/2 * n/2, which would be still O(n^2)

Is this correct?

Edit: curiously, the EDIT button is present in this post, but not in my previous.

## vashishta

actually
for each loop we can assume it is in the order of n or {0(n)}

## Taywin 312

By the way, non-sorted 2D array with nxm will have O(nxm) because you have no uniform rule to search, so you would try to look through the whole array. Average case to me is still O(nxm)...

For a sorted 2D array, it will easily become O(logn) regardless the m and n values. Or the exact time would be log2.

## amina imam

2 programs a and b that have performance as o(log n) and o(n),if each program requires 10 sec to solve a problem of size 1000,what is the time required for each to double.

## Taywin 312

3 weeks old thread. Better create a new post instead of hijack old post... Didn't even look at what I just posted earlier...

Hmm... Clever, you are. Post your homework question to get an answer...

## Rashakil Fol 978

2 programs a and b that have performance as o(log n) and o(n),if each program requires 10 sec to solve a problem of size 1000,what is the time required for each to double.

There's no way to answer the question.

## anirbanengg

Awesome Explanation .Definaitely I will copy that and keep it

## AlgoComplexity

awesome post!!!! very clear explanation.

## chandrabhu

``````f(m,n){
if(m%n==0)
return n;
else
m=m%n;
return f(m,m mod n);
``````

## Mehmet_3

``````Dim C(n) As Integer
AA(C, 1, n)
For  j  As Integer = 1 To n
Dim  i  As integer = Sqrt(j)
print C(i)
Next
Sub AA (C  As Integer(), m  As Integer, n  As Integer)
Dim  p  As Integer = (n-m+1)/3      n
If p > 5  Then                      n
For  i  As Integer = 1 to 4    n+1
AA (C, m, m+p)
Next
For  i  As Integer = m To n   n+1
C(i)=C(i)+1
Next
End If
End Sub
``````

## neufmartial

Hi Guys,

I know this thread is quite old but I have a question related to time complexity of the program. I have gone through each and every post in this thread, and found the discussion quite helpful and interesting.

I tried to write 2 searching program, one through linear search and another program comparing 2 times instead of 1 in the single iteration. My code is a below.

Using Linear Searching:

``````public class LinearSearching {

public static void main(String[] args) {
long startTime = System.currentTimeMillis();
//      int[] arr = {1,4,5,6,7,8,3,4,34,23,1,2,4,5};
//      int[] arr = {};
//      int[] arr = {1};
//      int[] arr = {99};
//      int[] arr = {1,4};
//      int[] arr = {1,4,3};
//      int[] arr = {1,4,3,5};
//      int[] arr = {1,4,3,7,5};
//      int[] arr = {1,4,3,11,23,45};
//      int[] arr = {1,4,3,67,88,66,77};
//      int[] arr = {1,4,3,45,33,44,22,33};
int[] arr = {1,4,3,11,23,45,1,4,3,11,23,45,1,4,3,45,33,44,22,33,1,4,3,67,88,
66,77,1,4,3,67,88,66,77,1,4,3,67,88,66,77,1,4,3,67,88,66,77,1,4,
3,67,88,66,77,1,4,3,67,88,66,77,1,4,3,67,88,66,77,1,4,3,67,88,66,77,
1,4,3,11,23,45,1,4,3,11,23,45,1,4,3,45,33,44,22,33,1,4,3,67,88,
66,77,1,4,3,67,88,66,77,1,4,3,67,88,66,77,1,4,3,67,88,66,77,1,4,
3,67,88,66,77,1,4,3,67,88,66,77,1,4,3,67,88,66,77,1,4,3,67,88,66,77};

System.out.println("The length of array = "+arr.length);

int noToFound =99;

int index = linearSearch(arr, noToFound);

if(index==-1) {
System.out.println("The number "+noToFound+
" cannot be found in array = "+
arr.toString());
} else {
System.out.println("The number "+noToFound+
" is found in array = "+
arr.toString()+" at index "+index);
}

long endTime = System.currentTimeMillis();

System.out.println(" Time taken for Linear searching = "+(endTime-startTime));
}

public static int linearSearch(int[] arr, int numberToFind) {
if(arr.length<1) {
System.out.println("The array is empty");
return -1;
}

for(int i=0; i<arr.length; i++) {
System.out.println("Iteration is = "+(i+1));
if(arr[i] == numberToFind) {
return i;
}
}

return -1;
}
``````

Another Searching Program:

``````public class BiLinearSearch {

public static void main(String[] args) {
long startTime = System.currentTimeMillis();
//      int[] arr = {1,4,5,6,7,8,3,4,34,23,1,2,4,5};
//      int[] arr = {};
//      int[] arr = {1};
//      int[] arr = {99};
//      int[] arr = {1,4};
//      int[] arr = {1,4,3};
//      int[] arr = {1,4,3,5};
//      int[] arr = {1,4,3,7,5};
//      int[] arr = {1,4,3,11,23,45};
//      int[] arr = {1,4,3,67,88,66,77};
//      int[] arr = {1,4,3,45,33,44,22,33};
int[] arr = {1,4,3,11,23,45,1,4,3,11,23,45,1,4,3,45,33,44,22,33,1,4,3,67,88,
66,77,1,4,3,67,88,66,77,1,4,3,67,88,66,77,1,4,3,67,88,66,77,1,4,
3,67,88,66,77,1,4,3,67,88,66,77,1,4,3,67,88,66,77,1,4,3,67,88,66,77,
1,4,3,11,23,45,1,4,3,11,23,45,1,4,3,45,33,44,22,33,1,4,3,67,88,
66,77,1,4,3,67,88,66,77,1,4,3,67,88,66,77,1,4,3,67,88,66,77,1,4,
3,67,88,66,77,1,4,3,67,88,66,77,1,4,3,67,88,66,77,1,4,3,67,88,66,77};

System.out.println("The length of array = "+arr.length);

int noToFound =99;

int index = biLinearSearch(arr, noToFound);

if(index==-1) {
System.out.println("The number "+noToFound+
" cannot be found in array = "+
arr.toString());
} else {
System.out.println("The number "+noToFound+
" is found in array = "+
arr.toString()+" at index "+index);
}

long endTime = System.currentTimeMillis();

System.out.println(" Time taken for Bi-Linear searching = "+(endTime-startTime));
}

public static int biLinearSearch(int[] arr, int noToBeFound) {
int lower = 0;
int higher = arr.length;

if(higher==0) {
System.out.println("The array is empty");
return -1;
} else if(higher==1) {
// Compare the numbers
if(arr[0] == noToBeFound) {
return 0;
} else {
return -1;
}
}

while(lower<higher) {
// Get the middle value
System.out.println("The iteration is "+(lower+1));
if(arr[lower] == noToBeFound) {
return lower;
} else if(arr[higher-1] == noToBeFound){
return higher-1;
} else {
lower++;
higher--;
}
}

return -1;
}
}
``````

I tried running these 2 programs with the sample data as mentioned in the commented code. I found that the loop in the second program runs almost half time to the value of n (n is the number of elements in array).

I also printed out the actual execution time which is as follows:

For Linear Search:

``````The number 99 cannot be found in array = [I@2dcc7e1d
Time taken for Linear searching = 48
``````

For Another Search:

``````The number 99 cannot be found in array = [I@2dd17e01
Time taken for Bi-Linear searching = 1
``````

As you can see from above results that the time taken by second program is much less that that by the first program.

Now I know that the time complexity of a linear searching in worst case is O(n). I am confused about the second method though. Can anyone please help me to understand the time complexity for second method?

From my understanding in the second program the loop runs for half the number of times of n (n being number of elements in array).

So the time complexity in worst case for second program will be O(n/2) which is again equal to O(n).

Can anybody please clarify if I am right or wrong here?

Also if the time xomplexity of both the methods is O(n), then how is the second method runs faster than the linear search method?

Any help is appreciated.

Thanks & Regards,
Neuf

## deceptikon 1,790

Also if the time xomplexity of both the methods is O(n), then how is the second method runs faster than the linear search method?

Big O only tells you the expected growth rate of the algorithm, which in both cases is indeed O(n), not its actual execution performance. Algorithms with the same complexity can run in wildly different times because at execution time the constants matter.

## neufmartial

Big O only tells you the expected growth rate of the algorithm, which in both cases is indeed O(n), not its actual execution performance. Algorithms with the same complexity can run in wildly different times because at execution time the constants matter.

@deceptikon.... Thanks for your reply. Just for my understanding, it means that the time complexity that we find using Big-Oh, Omega or Theta is not the actual execution time of the program?

Also which method will be best from the above two methods, since the time complexity is same for both methods? The second method looks pretty fast compared to first method. Also the space required by second program will be more, so which method should be preferred?

Thanks & Regards,
neufmartial

## deceptikon 1,790

Just for my understanding, it means that the time complexity that we find using Big-Oh, Omega or Theta is not the actual execution time of the program?

Correct. The two are related, but not 1-to-1.

Also which method will be best from the above two methods

'Best' is subjective as it depends on your needs. However, if you're looking for execution performance with only those two options, I'd say the second is superior since you've already profiled it to be faster. ;) Further, by not removing constants you can more accurately judge the real performance difference of two algorithms. O(n) is extremely likely to be slower than O(n/2). The question at that point is how much slower, and deeper analysis of the work done at each iteration is needed to determine how significant that difference is.

Also the space required by second program will be more

The space difference is tiny and constant (one `int` variable), so I'd call it negligible unless you're working with an exceptionally limited environment.

## neufmartial

@deceptikon.... Thanks for explaining the things. I am kinda beginner in this subject. Can you point me to some of the good links which is easy to understand?

## deceptikon 1,790

Complexity theory isn't easy unless you're a math whiz. I always preferred a more practical approach, which I've described here. But it looks like you already have those basics essentially down, and that article doesn't really delve into when and why to apply complexity analysis.

Most other reasources I've seen are heavy on the math and light on practical usage, though this blog was a refreshing read.

## Labiga

what will be the complexity of An Area of a circle

## AssertNull 1,094

what will be the complexity of An Area of a circle

1. Most people write it as O(1), but since the constant doesn't matter, stick in your favorite number. No variables. Multiply the radius times itself, then times PI. Constant time.

Well this is weird. My "42" in paragraph above turned into "1". Accidently parsing a leading number as a list?

## jamie_13

In computer science, the time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the length of the string representing the input.