Like Tree11Likes
  • 2 Post By laserlight
  • 1 Post By stevesmithx
  • 1 Post By Neo1
  • 1 Post By grumpy
  • 3 Post By phantomotap
  • 1 Post By Neo1
  • 2 Post By grumpy

How O(log n) time is calculated?

This is a discussion on How O(log n) time is calculated? within the General Discussions forums, part of the Community Boards category; I know Binary Search has O(log n) complexity because we don't go on checking every values to search like Linear ...

  1. #1
    Registered User
    Join Date
    Mar 2013
    Posts
    24

    How O(log n) time is calculated?

    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?

  2. #2
    Registered User
    Join Date
    Apr 2013
    Posts
    1,313
    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).

  3. #3
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,886
    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.

    Quote Originally Posted by dotnet13
    I know Binary Search has O(log n) complexity because we don't go on checking every values to search like Linear Search.
    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)?
    grumpy and phantomotap like this.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  4. #4
    Registered User
    Join Date
    Mar 2013
    Posts
    24
    Quote Originally Posted by laserlight View Post
    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)?
    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?

  5. #5
    and the hat of copycat stevesmithx's Avatar
    Join Date
    Sep 2007
    Posts
    500
    Quote Originally Posted by dotnet13 View Post
    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?
    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.
    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?
    grumpy likes this.
    Not everything that can be counted counts, and not everything that counts can be counted
    - Albert Einstein.


    No programming language is perfect. There is not even a single best language; there are only languages well suited or perhaps poorly suited for particular purposes.
    - Herbert Mayer

  6. #6
    Registered User
    Join Date
    Mar 2013
    Posts
    24
    Quote Originally Posted by stevesmithx View Post
    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.
    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 search

  7. #7
    Internet Superhero
    Join Date
    Sep 2006
    Location
    Denmark
    Posts
    964
    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?
    dotnet13 likes this.
    How I need a drink, alcoholic in nature, after the heavy lectures involving quantum mechanics.

  8. #8
    Registered User
    Join Date
    Jun 2005
    Posts
    6,425
    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).
    Salem likes this.
    Right 98% of the time, and don't care about the other 3%.

  9. #9
    Registered User
    Join Date
    Mar 2013
    Posts
    24
    Quote Originally Posted by grumpy View Post
    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.
    Last edited by dotnet13; 05-04-2013 at 10:00 AM.

  10. #10
    Master Apprentice phantomotap's Avatar
    Join Date
    Jan 2008
    Posts
    4,332
    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

  11. #11
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,886
    Quote Originally Posted by dotnet13
    all I asked is any simple example which will help me to understand clearly
    A simple example that you can use is binary search. However, you wrote:
    Quote Originally Posted by dotnet13
    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
    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).

    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:
    Quote Originally Posted by dotnet13
    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?
    (emphasis mine)
    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.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  12. #12
    Internet Superhero
    Join Date
    Sep 2006
    Location
    Denmark
    Posts
    964
    Quote Originally Posted by dotnet13 View Post
    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.
    We need a "Best of CBoard" thread for these kind of replies, we really do!
    AndiPersti likes this.
    How I need a drink, alcoholic in nature, after the heavy lectures involving quantum mechanics.

  13. #13
    Registered User
    Join Date
    Jun 2005
    Posts
    6,425
    Quote Originally Posted by Neo1 View Post
    We need a "Best of CBoard" thread for these kind of replies, we really do!
    There's a secret handshake to get into the forum where such things are discussed
    Neo1 and laserlight like this.
    Right 98% of the time, and don't care about the other 3%.

  14. #14
    and the hat of copycat stevesmithx's Avatar
    Join Date
    Sep 2007
    Posts
    500
    Quote Originally Posted by dotnet13 View Post
    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.
    Graph of a function - Wikipedia, the free encyclopedia
    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.
    Not everything that can be counted counts, and not everything that counts can be counted
    - Albert Einstein.


    No programming language is perfect. There is not even a single best language; there are only languages well suited or perhaps poorly suited for particular purposes.
    - Herbert Mayer

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 2
    Last Post: 04-17-2013, 12:25 AM
  2. Calculated values coming out strange
    By svisger in forum C Programming
    Replies: 5
    Last Post: 03-02-2011, 12:49 PM
  3. Value not calculated
    By RicOz6 in forum C Programming
    Replies: 5
    Last Post: 02-11-2011, 05:35 PM
  4. The highest Fibonacci number ever calculated
    By dwks in forum C Programming
    Replies: 19
    Last Post: 07-27-2005, 05:57 PM
  5. How are s&t calculated on a NURBS surface?
    By BrianK in forum Game Programming
    Replies: 1
    Last Post: 12-04-2002, 10:48 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21