Big O () Performance for a searching algorithm in a circle: 1 unidirectional, 2- Bidirectional

Question

1.00/5 (1 vote)

See more:

If I have n element organized in sequence is a circle as x1, x2, x3,..,xn and the circle wraps around: xn will be followed by x1.
Each element can perform a search for any other element.
Each element can forward the query to its adjacent neighbor.

What is the performance of searching for an element xm in this circle if:
1- I allow the search to be in one direction only. i.e.: if Xi is searching for Xm, the search can only proceed sequentially from Xi-->Xi+1-->Xi+2... until Xm is found.

2- I allow the search to be bi-directional. i.e.: each element can forward the query either way. If Xi is searching for Xm, the query could go either: Xi-->Xi+1-->Xi+2...-->Xm or Xi-->Xi-1-->Xi-2...-->Xm

My intuition is that for the first case the worst case is if xm=xn ==> O(n) and for the second one the worst case would be if xm is in the middle between x1 and xn ==> is O(n/2)

Note: I can determine which direction the search can go for the second case. For example: If I put the positive elements on right side and the negative elements on the other side and I am performing my search from an element with the value 0. Element 0 knows that if the element I am looking for is positive I should search on the right. etc.

Posted 11-Jan-15 6:20am

Member 11367110

Updated 11-Jan-15 7:19am

v4

Add a Solution

Comments

[no name] 11-Jan-15 12:45pm

I don't understand it completely, but no, my Intuition is not xn==>O(n/2), because the order remains the same.
And yes Math and Intuition is a potential of conflict....one of my teacher told me that :-)
Bruno

Member 11367110 11-Jan-15 12:55pm

if the worst case scenario for the first one is when xm is the last element in the circle. Then the worst case of the second case is that when xm is in the middle of the circle. Right? It could not be the last element as the previous case otherwise I would reach it in one step only from the other side.
What do you think?

Sergey Alexandrovich Kryukov 11-Jan-15 13:28pm

No, this is not related to the order, and the answer will remain O(N). Please see Solution 1 and 2.
—SA

Sergey Alexandrovich Kryukov 11-Jan-15 13:00pm

The description is incomplete. You need to specify the problem more precisely.
—SA

Member 11367110 11-Jan-15 13:20pm

I hope I made it clear.

Sergey Alexandrovich Kryukov 11-Jan-15 13:29pm

Well, better, thank you; please see the answer.
—SA

2 solutions

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Kornfeld Eliyahu Peter · Answer 1 · 2015-01-11T07:04:00

Solution 1

I can't see the difference... O(n) means that (in worst case) you have to visit every node to get the answer.
It does not changes if you check it from the beginning to the end or from both end to the middle...
As to check one item is a constant time and you ave to check all items (in worst case) in both method there is no difference and bot have a maximum of O(n)...

Posted 11-Jan-15 7:04am

Kornfeld Eliyahu Peter

Comments

Sergey Alexandrovich Kryukov 11-Jan-15 13:28pm

Exactly, a 5. Please see also my answer. (By some reason, I did not see yours, probably because of long break. :-)
—SA

Kornfeld Eliyahu Peter 11-Jan-15 13:29pm

Thank you...

Sergey Alexandrovich Kryukov · Answer 2 · 2015-01-11T07:27:00

Solution 2

In all your cases, the time complexity is still O(N). Here is why: to find just one element, in worse-case scenario you still have to test all elements one by one. The search in different directions or starting the search from another element changes nothing.

Also, you should see the difference between complexity and performance. Big-O is the measure of complexity, not performance. For example, you can search in N fragments at the same time using N separate CPU cores. It would improve the performance by the factor of N minus some overhead for implementation of parallel mechanism. But it would not improve complexity.

—SA

Posted 11-Jan-15 7:27am

Sergey Alexandrovich Kryukov

Comments

Member 11367110 11-Jan-15 13:58pm

I am having difficulty explaining in english.
I have 9 numbers: 4 3 2 1 0 -1 -2 -3 -4 they are placed in a circle. Consider them as addresses. that means: every element knows that it has a neighbor that is greater in value on the left, and another neighbor that is smaller in value on the right.
If for example element 0 wants to send a message to element 2, it knows it has to go 2 steps on the left. And if it is searching for -3, it knows it has to go 3 steps on the right.
IN that case, the worst case scenario would be for element 0 is to search for element 4 or -4, which is 4 steps either way.
Now, Comparing to the first scenario, which one performs better? Should not the second one takes half the time of the first one?

Sergey Alexandrovich Kryukov 11-Jan-15 14:08pm

No difference, unless you introduce processing by several CPU code. More exactly, more the first, simpler algorithm will show better performance.
—SA

Member 11367110 11-Jan-15 14:44pm

Thank you.
How about the average lookup time?
Would not that be less for the second one?

Sergey Alexandrovich Kryukov 11-Jan-15 15:07pm

No, why? More exactly, it will be faster if you parallelize. It could be TPL for Windows or .NET, or the like. It will only really improve throughput if you actually have as many CPUs/cores. But it can be still slower for small sets, because of some overhead. You can test it all on some particular implementation, for research/educational purposes.
—SA

Member 11367110 11-Jan-15 15:56pm

Please bear with me:
If I have 64 elements arranged in a 2 dimensional space (8*8). Each element has 8 neighbors and the system wraps around. (01 can forward to 02 10 09 08 57 58 64 16) like shown. would not the routing performance be log n

01 02 03 04 05 06 07 08
09 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24
25 26 27 28 29 30 31 32
33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48
49 50 51 52 53 54 55 56
57 58 59 60 61 62 63 64

Sergey Alexandrovich Kryukov 11-Jan-15 16:04pm

You did not mentioned anything of rank 2 in your original question. This is a different problem, but the solution is the same. You cannot reduce time complexity if you have unstructured set. Please understand: this matrix set is exactly as unstructured as the circle. You still have to go to each element in worst-case scenario. The time complexity is only reduced by using some sorted order or partial order of elements, be it a sequence, a tree, or anything else. For fully random unordered data, there is no difference how you arrange it.
It's still O(N) where N is the total number of elements, no matter how they are arranged. For N x N elements, its O(N*N), and so on. You are not suggesting any factor for reducing of time complexity.

Look, in all these attempts, you are probably missing something basic and simple.

—SA

BillWoodruff 11-Jan-15 16:55pm

I think knowing the data is ordered in this way really changes the original question so much that you need to re-write the original question.

Member 11367110 11-Jan-15 16:23pm

I took algorithms 13 years ago.
I thought I was assuming order. The addresses are ordered in specific sequences. Horizontal the space is 1, vertical it is 8, diagonal it is 9..
My understanding is that if I am looking for any address I shall walk on a straight line of addresses. And any line is (log n). I mean: first locate the direction, then walk the whole line either to left, right, diagonal..

Sergey Alexandrovich Kryukov 11-Jan-15 18:12pm

You cannot assume anything, should specify everything. Even if you have some order, you need to explain how you are using it.
—SA

Member 11367110 11-Jan-15 18:36pm

I am sorry if i can not express well in english. I did specify. I emphasize that Data is ordered as I mentioned.
Would that help?
Say 64 needs to forward a segment to 57, it knows that it is on its left. or if it will send something to 16, it knows that 08 is vertically positioned. and they both 8 steps away from 64.

Thank you

Sergey Alexandrovich Kryukov 11-Jan-15 19:21pm

The question is simple: is data ordered or not? In other words, the algorithm can be improved if you have a choice not to move from element N to element M, can also infer: if element N and M does not match the search criteria, then all elements between N and M don't match, no need to check them up. Only in such cases you can make the algorithm faster.

To me, it looks like you mix up different things: ordering the elements according to the search criteria, and structural ordering. Let's consider the array. You can always jump from one element to any other element, just because the elements sit in continuous location in memory (or the situation is logically equivalent to that). So, "finding" of the element by index if always O(1) (in contrast to non-indexed linked list, where this is O(N)). But if you have some search criteria not bound to the array index, your search would take O(N). Same thing with all other structures. As your concern is not the performance of the navigation in some structure, not the search criteria, structure does not help (but could make things worse). Maybe, you don't confuse those things; I don't know, but my impression is that you are confused.

Another thing you are not making clear (I an not sure if you are personally confused with it) is two very different things: 1) the problem if finding some big-O measures of some given algorithm and 2) finding better algorithm and determining if some better algorithm is possible. You are seemingly mix these two problems together.

—SA

Member 11367110 12-Jan-15 2:28am

The elements are structured and ordered. Similar to your array point: I can move from one element to another in O(1). because I exactly know where the element is and I know it is there.
Now consider this: My elements are addresses. They are THERE. There is always a query Hit. If I am going from A to B, I always know I will find B. And I know that B is away from A within fixed steps based on the addressing I am using. Also, if I want to go from A to B, I immediately know which direction or which path (from the eight paths) I would go to reach B. So the way I see is is that to choose the direction is O(1), and to walk through the path to reach the worst case scenario is log n since the system is n.

Thank you

Sergey Alexandrovich Kryukov 12-Jan-15 14:11pm

You just conformed that there is a structural order (which just cannot be not be there, anyway), and did not say a word about order according to search criteria. Here we go again.
—SA

Member 11367110 12-Jan-15 14:45pm

That is the order I mentioned previously. 64 addresses ordered as shown. nothing else.
I found a similar problem, with routing cost n^1/2 if the system does not wrap, and 1/2 n^1/2 if the system wraps.

Sergey Alexandrovich Kryukov 12-Jan-15 14:56pm

If they are the same values as in the example, there is not need to search anything at all (O(1):-)
If you are talking about the search, you need to explain what are they in general case. Are they just arbitrary numbers but ordered in the same way as those example (by >= order)? If so, the correct search algorithm gives you O(log N).
—SA

Member 11367110 12-Jan-15 15:02pm

Can I give you my skype ID to explain my point there?

Sergey Alexandrovich Kryukov 12-Jan-15 15:13pm

Sorry, I don't have much time for that. Everything can be explained in words.
—SA

Member 11367110 12-Jan-15 15:28pm

They are just ordered addresses. No values. There is no search. Just routing from point A to point B based on the arrangement above. That is the only ordering. It is just like that.
If 55 is routing a segment to 12, it deduces that it needs to forward it to 46. 46 will fwd to 37-> 28-> 20-> 12.
OR: 55-> 62-> 05-> 12
That what I meant when I said that the worst case scenario is when the element is exactly in the middle. Becuase if 62 is fwd to 06, it can reach it in one step only.
thats why I think it is most likely 1/2 n^1/2
There is no splitting in half each step. The fwd goes step by step through the path.

Sergey Alexandrovich Kryukov 12-Jan-15 15:42pm

"No search" always means O(1).
May I ask you: is it possible that, instead of asking the questions on all cases, you could master calculation of big-O measure yourself? :-)
—SA

Member 11367110 12-Jan-15 15:53pm

I am working on it.
O(1) if all elements know about each other.
My case is not. Each element knows about 8.
Thank you for your help.

Sergey Alexandrovich Kryukov 12-Jan-15 16:34pm

No, O(1) simply means that the number of operations asymptotically the same, does not depends on the size of the set. It is not directly related to relationships between elements. I have no idea what "knows about 8". If it means: has direct access to 8 elements, it simply means that the data structure is poorly organized (especially for 8x8 :-)... So, are you saying that all addresses (they are values, in fact) are random numbers? (It means, unordered.) Then the answer is: O(N). It's all simple.
—SA

Member 11367110 12-Jan-15 18:40pm

I wish it was O(1).
It would be O(1) if this is a completed graph. In that case any element would reach any other one in one single step.
Probably here where I was not able to explain properly: when I said 1/2 n^1/2 I meant by that the number of steps to go.
Knows about 8 means: every element knows its surrounded by eight specific elements, it knows their addresses. How do they get there in this structure is not important. Once an element fwd a msg to its neighbor, it does not care how the neighbor will fwd: it just does not know. it is the neighbor's responsibility to fwd it in the correct direction.
And again, they are NOT random at all. They are as they are ordered.
It is my fault that I was confused about the question. Probably as you said about manythings.

Sergey Alexandrovich Kryukov 12-Jan-15 19:17pm

If was if it was, as you say, there is no search. But I guess there is the choice. Look, why no simply using 8 x 8 array. At least then the would not be an artificial problem of access. Now, if the values are ordered (again, ordered by search criteria; and addresses are still values), then this is O(log N). More exactly, if would be if you gave up pointless knows-8 design.
—SA

Member 11367110 13-Jan-15 2:43am

Why the fwd will go through all elements in worst case? You are still doubting the order of the elements. I am assuring you that they are ordered in someway. I do not think it can be O(n).

Sergey Alexandrovich Kryukov 13-Jan-15 2:54am

I didn't say you have to go through all of them if there is ordering of values by sorting criteria. You have to, if they are unsorted. If you had random indexing for any element (you should, in practice!), the answer is O(log N). Or O(N) is unsorted. Why are we repeating same things over and over? I guess, you simply need to figure out where those big-O metrics come from, otherwise we'll never finish.
—SA

Member 11367110 13-Jan-15 3:36am

The similar thing I found was in peer to peer systems. It is application for structured p2p called CAN: 1/2 n^1/2
it is very similar.
I really appreciate your help.

Sergey Alexandrovich Kryukov 13-Jan-15 10:56am

Look, may be I'm missing something? Maybe your problem is not calculation, but some other process (controlling some machine moving some from one note to another)? What this p2p (network?) does? Did you mention it from the very beginning?
—SA

Member 11367110 13-Jan-15 18:00pm

I would like sharing with you. Thats why I asked you for a contact info.

Sergey Alexandrovich Kryukov 13-Jan-15 18:39pm

You can find my personal contact page on my site, which you can find through my CodeProject profile. You can contact me; however, I cannot promise anything certain, sorry.
—SA