Printable View
I know Binary Search has O(log n) complexity because we don't go on checking every values to search like Linear Search. But Im still not sure how O(log n) is calculated for other programs, I mean how am I suppose to know whether it has a logarithmic growth?
In some cases the loops within an algorithm can be converted into an equivalent mathematical formula to calculate the complexity. In other cases, additional counters can be placed in the code in order to determine the number of iterations versus some input criteria, such as n = number of elements to be processed versus the number of iterations of the code (including recursions).
While this is about algorithmic complexity, which is certainly related to programming, it is not about C programming per se, so I am moving this to General Discussions.
Suppose my algorithm checks every other value. This means that "we don't go on checking every values to search like Linear Search". Does it mean that the time complexity of my algorithm is O(log n)?Quote:
Originally Posted by dotnet13
that is what I wanted to know, if Im scanning through every element in a list/array the worst case will be O(n) because the element can be at the last position and don't try to confuse me with a smartass answer and it doesn't help at all. In Binary search Im scanning depending on the mid value, so there is no need to check all the value thus it throws away half of the value to scan. But my question was how log n complexity is calculated?Quote:
Originally Posted by laserlight
I understand that laserlight's post didn't answer your question directly. But then again, it was not meant to confuse, but confuzzle you so that you will be on the right path to get the answer that you seek.Quote:
Originally Posted by dotnet13
To answer your question, here's a hint: Use a graph and plot N(total number of elements) against X(the number of searches required in the worst case) in a binary search. Notice anything?
I dont know what you are saying, but for a N x M matrix it become O(n log m) since there are N rows and for every row it's log m, if we apply Binary searchQuote:
Originally Posted by stevesmithx
Consider this: For each iteration the amount of entries where the target value can be present is halved. So after the first iteration there will be n/2 entries remaining, then n/4, then n/8 and so on. In the worst case scenario, this continues until there is only one entry left, ie. n/x = 1, where x is 2 to the power of the number of iterations. So, given any number n, how many iterations can be performed before n/x = 1?
laserlight and stevesmithx have both addressed your problem. You need to work a little harder to understand the answers given, rather than expecting to be spoon-fed.
Laserlight did somewhat indirectly, by pointing out that your explanation of why a binary search is O(log n) is flawed (in fact, she gave a counter-example). If you can't understand the logic of that, you also won't understand the logic of working out what complexity some other algorithm has.
Stevesmithx's point is that the simple act of plotting a graph would be one way of doing the analysis you asked about (albeit an informal one). Plotting graphs on paper is something that I learned primary school maths class, and I doubt I'm unique in that. If you can't understand a method based on plotting graphs, you will certainly not understand more formal approaches (e.g. a mathematical derivation or an algorithm description).
What are you? Einstein of Algo? I don't think so, if you're that good then why you are spending time in a forum, why don't you make a new Programming Language or work for Google/Microsoft? You're not that good I guess? Did you understood algo analysis in one day? I don't think so either. And who is spoon-feeding who? I don't know what relation you have with the C++ witch or laserlight, but you tend to like whatever he/she says. it's kinda biased. I didn't ask for code or give graphical illustration, all I asked is any simple example which will help me to understand clearly "Suppose my algorithm checks every other value. This means that "we don't go on checking every values to search like Linear Search". Does it mean that the time complexity of my algorithm is O(log n)?" - is that suppose to mean indirectly what? Horse........? And Stevesmithx's wasn't very clear at all, there many graph related problems ? Did you ever heard graph theory? Maybe not? Because someone who brags about understanding plotting graph at school level is unlikely to understand those. I had A+ and A in my school and high school as well as good grades on programming and algo subject, so what? Want to see it? I will send it via mail if you want. And who said I do not understand derivation or algo description? How much do you know about me? Nothing. Don't criticize anyone without knowing properly. If forums can't help people then why they are good for? I am assuming after posting this reply I will probably get banned, cause if the moderators of a forum are airheaded then it is very much expected. Well it doesn't matter at all, there are many good forums with much intelligent people are out there.Quote:
Originally Posted by grumpy
O_o
Congratulations.
You have passed the secret initiation test.
We have been looking for an entitled newbie capable of mindlessly regurgitate insults for a secret mission.
You are the chosen one.
Your task, should you choose to accept it, is to head to Saffron Walden where the man Furlo Roth will seek you out when you have gained the trust of the Saffron Walden community. He will have more information at that time.
DO NOT FORGET Berwhale!
Soma
A simple example that you can use is binary search. However, you wrote:Quote:
Originally Posted by dotnet13
Reading that, I suspected that you do not actually understand why binary search has a time complexity of O(log n). I wanted to get you think a bit further on your explanation for why binary search has such a time complexity, so I presented a case where it satisfies the reason you gave, yet the time complexity is not O(log n).Quote:
Originally Posted by dotnet13
Instead of accusing me of trying to confuse you, you could have taken this was an opportunity to exercise what you already know concerning complexity. For example, you could say: I check about n/2 of the values, assuming n values. O(n/2) is still in O(n), hence the time complexity of my algorithm is O(n), not O(log n), so the answer is no.
Once you arrive at this conclusion, the next step is to question your own explanation of binary search's time complexity since you have seen a counterexample. In a way, you did do so:
(emphasis mine)Quote:
Originally Posted by dotnet13
I note that your question was not how "how log n complexity is calculated", but rather how it should be calculated for "other programs" besides binary search. Apparently, you changed tack and realised that you don't know for binary search either. That is good, because once you know what you don't know, you can begin to find out what you don't know.
Now, the part that I placed in bold illustrates that you are on the right path. You intuitively saw that "throwing away" half of the values to scan has something to do with it being O(log n) rather than O(n). Yet in my counterexample, I also "throw away" half of the values to scan. The difference then, is that for binary search, this happens on each step. It would have been good if you could have seen this yourself, but I see that Neo1 pointed it out to you in post #7.
We need a "Best of CBoard" thread for these kind of replies, we really do!Quote:
Originally Posted by dotnet13
There's a secret handshake to get into the forum where such things are discussed ;)Quote:
Originally Posted by Neo1
Graph of a function - Wikipedia, the free encyclopediaQuote:
Originally Posted by dotnet13
Graph theory - Wikipedia, the free encyclopedia
Not the same.
Also, How To Ask Questions The Smart Way (also linked in laser's sig) should give an idea about how forums work.