Thread: Analyzing time complexity of my code

  1. #1
    Registered User
    Join Date
    Apr 2015
    Posts
    485

    Analyzing time complexity of my code

    Hi guys, I'm just wondering when we are neglecting time complexity of something and when not? to clear more about an example, lets say I have a merge_sort recursively, when calling in this pattern Merge_Sort(Array A, q+p, r) which q is median and p,r are bounds of the array .. we are neglecting the consume time of argument q+p while adding .. why?! and when we are neglecting like these things and when not ?

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    36,835
    Post your code.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    26,230
    I think you might benefit from reading some structured material on time complexity that would explain this to you.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  4. #4
    Registered User
    Join Date
    Apr 2015
    Posts
    485
    Quote Originally Posted by Salem View Post
    Post your code.
    As you wish;
    Code:
    Merge_Sort(A ,p, r)
    {
    if (p<r)
    q=(r+p)/2;
    Merge_Sort(A,p,q);
    Merge_Sort(A,q+1,r);
    Merge(A,p,q,r) // thats function is merging two arrays of size n
    }
    How could I analyze the time complexity? I don't know which code's rows can be neglected and which not in calculating the time complexity ... thank in advance

  5. #5
    Registered User
    Join Date
    Apr 2015
    Posts
    485
    Quote Originally Posted by laserlight View Post
    I think you might benefit from reading some structured material on time complexity that would explain this to you.
    Hi laserlight, I already have read the idea of time complexity but I'm not understanding when we can neglect time rather than the other time and vise versa ... as a result I posted here my thread in a hope to help!

    thanks

  6. #6
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    36,835
    Time complexity is a property ascribed to algorithms, not implementations.

    Merge sort is Ο(n log n) regardless of how it is implemented.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Time complexity.
    By RyanC in forum C Programming
    Replies: 1
    Last Post: 07-10-2015, 01:18 PM
  2. Replies: 1
    Last Post: 02-05-2014, 11:03 PM
  3. question about code's time complexity
    By nik in forum C++ Programming
    Replies: 2
    Last Post: 03-06-2011, 03:21 PM
  4. need help with analyzing some code
    By happyclown in forum C Programming
    Replies: 7
    Last Post: 01-30-2009, 08:00 AM
  5. Analyzing Code
    By smitsky in forum C++ Programming
    Replies: 13
    Last Post: 01-12-2005, 05:33 PM

Tags for this Thread