Time complexity of algorithm - Page 4

Question

deceptikon 1,790 Code Sniper

9 Years Ago

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.

Reply to this topic

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.

Narue 5,707 Bad Cop Team Colleague · Answer 1 · 2010-09-13T19:36:45+00:00

>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 0 Newbie Poster · Answer 2 · 2010-09-13T23:53:44+00:00

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

HeyBuddy 0 Newbie Poster · Answer 3 · 2011-01-19T02:55:19+00:00

HeyBuddy 0 Newbie Poster

13 Years Ago

...

Edited 13 Years Ago by HeyBuddy because: n/a

mridul_018 0 Newbie Poster · Answer 4 · 2011-03-02T10:43:43+00:00

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 Super Senior Demiposter Team Colleague · Answer 5 · 2011-03-02T10:45:44+00:00

Rashakil Fol 978 Super Senior Demiposter

13 Years Ago

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

Cowst · Answer 6 · 2011-05-14T05:09:32+00:00

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 · Answer 7 · 2011-05-15T19:45:05+00:00

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 0 Newbie Poster · Answer 8 · 2011-09-22T18:45:20+00:00

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

Taywin 312 Posting Virtuoso · Answer 9 · 2011-09-22T23:03:30+00:00

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.

amina imam 0 Newbie Poster · Answer 10 · 2011-10-14T19:06:22+00:00

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 Posting Virtuoso · Answer 11 · 2011-10-14T19:24:03+00:00

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 Super Senior Demiposter Team Colleague · Answer 12 · 2011-10-15T17:25:48+00:00

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 0 Newbie Poster · Answer 13 · 2013-03-29T17:32:30+00:00

Awesome Explanation .Definaitely I will copy that and keep it

AlgoComplexity 0 Newbie Poster · Answer 14 · 2013-08-04T01:47:02+00:00

AlgoComplexity 0 Newbie Poster

10 Years Ago

awesome post!!!! very clear explanation.

Edited 10 Years Ago by AlgoComplexity

chandrabhu 0 Newbie Poster · Answer 15 · 2014-09-03T02:50:46+00:00

chandrabhu 0 Newbie Poster

9 Years Ago

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

Edited 9 Years Ago by Dani because: Formatting fixed

Mehmet_3 0 Newbie Poster · Answer 16 · 2014-12-22T04:07:05+00:00

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

neufmartial 0 Newbie Poster · Answer 17 · 2015-03-17T09:55:08+00:00

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 Code Sniper Team Colleague Featured Poster · Answer 18 · 2015-03-17T10:37:48+00:00

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 0 Newbie Poster · Answer 19 · 2015-03-17T11:33:59+00:00

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

neufmartial 0 Newbie Poster · Answer 20 · 2015-03-20T10:48:19+00:00

@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 Code Sniper Team Colleague Featured Poster · Answer 21 · 2015-03-20T16:34:09+00:00

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 0 Newbie Poster · Answer 22 · 2016-11-27T13:48:50+00:00

what will be the complexity of An Area of a circle

AssertNull 1,094 Practically a Posting Shark · Answer 23 · 2016-11-27T14:56:17+00:00

what will be the complexity of An Area of a circle

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 0 Newbie Poster · Answer 24 · 2017-04-21T04:30:57+00:00

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.