0

>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.

0

>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.

-1

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?

-1

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?

0

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.

Edited by Cowst: Just a comment

0

4+ months old thread from the previous reply post (above mine)...

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.

Edited by Taywin: n/a

0

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.

0

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...

0

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.

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

Edited by Dani: Formatting fixed

0

how about recursive algorithm?

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

Edited by Mehmet_3

0

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

0

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.

0

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

1

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.

0

@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?

0

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.

0

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?

Edited by AssertNull

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.