Thread: How to implement array with space complexity O(1)

  1. #1
    Banned
    Join Date
    Apr 2015
    Posts
    596

    How to implement array with space complexity O(1)

    Hi guys, how can I do an array with space complexity O(1) ?
    if I do it by constant compiler time like "int arra[20] " it takes O(n) and not O(1) .. maybe here I'm wrong about that but at least that what I've realized...

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,352
    Who told you "to implement array with space complexity O(1)"?

    Anyway, I'd say that what you're missing is that 20 is a constant, i.e., no matter how large your input, you still only have space for 20 ints, so the space complexity is constant.
    Last edited by laserlight; 12-31-2018 at 07:49 AM.
    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

  3. #3
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    38,741
    I'm wondering whether RyanC is a native English speaker.
    Because the buzzword bingo he keeps posting looks like the mangled ramblings of google translate, rather than coherent thought.

    No, you can't implement arr[n] in anything less than O(n) space.
    Pauli exclusion principle - Wikipedia
    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.

  4. #4
    Banned
    Join Date
    Apr 2015
    Posts
    596
    Quote Originally Posted by laserlight View Post
    Who told you "to implement array with space complexity O(1)"?

    Anyway, I'd say that what you're missing is that 20 is a constant, i.e., no matter how large your input, you still only have space for 20 ints, so the space complexity is constant.
    None, but lemme ask you , should be take the space complexity of a given array?! meaning with this, if there's an assignment which telling you to do ..."something" .. with space complexity space O(1) and already given two arrays ..so should you take the two given arrays into consideration of space complexity? or actually we just calculating the complexity space of what're going to do and not what's given?!

    thanks

  5. #5
    Registered User
    Join Date
    Dec 2018
    Posts
    38
    I can't believe people still respond to this entity. It's pointless.

  6. #6
    Registered User
    Join Date
    May 2009
    Posts
    4,069
    Quote Originally Posted by Salem View Post
    I'm wondering whether RyanC is a native English speaker.
    Because the buzzword bingo he keeps posting looks like the mangled ramblings of google translate, rather than coherent thought.
    I was wondering if he was a very young genius or an AI program.

    Tim S.
    "...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.." Bill Bryson

  7. #7
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,352
    Quote Originally Posted by RyanC
    None, but lemme ask you , should be take the space complexity of a given array?! meaning with this, if there's an assignment which telling you to do ..."something" .. with space complexity space O(1) and already given two arrays ..so should you take the two given arrays into consideration of space complexity? or actually we just calculating the complexity space of what're going to do and not what's given?!
    You basically ignored what I wrote and then came up with a hypothetical scenario that either won't happen or conforms to what I wrote. If it does happen and doesn't conform to what I wrote: go ask your instructor what on earth is going on.

    Quote Originally Posted by bruteforce
    I can't believe people still respond to this entity. It's pointless.
    It is a legit compsci question, I suppose, except that I don't want to fuel his wild thinking with more random ideas on how it is legit.

    Quote Originally Posted by stahta01
    I was wondering if he was a very young genius or an AI program.
    Neither. I think he's just a learner who likes to do a shotgun approach, which I guess works for some people, except that then he couples it with either missing what's obvious, or overthinking it until he feels compelled to post instead of just taking a nap.
    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

  8. #8
    Banned
    Join Date
    Apr 2015
    Posts
    596
    Quote Originally Posted by laserlight View Post
    You basically ignored what I wrote and then came up with a hypothetical scenario that either won't happen or conforms to what I wrote. If it does happen and doesn't conform to what I wrote: go ask your instructor what on earth is going on..
    maybe you miss understood and that's why you think I'm ignoring what've wrote !
    I'm asking if I have a function for instance String(char A[40], int size) , my question are we taking into consideration the given array for calculating the time complexity/space of that function? or we just assuming it as given and it doesn't take time at all?!

  9. #9
    Registered User
    Join Date
    Dec 2018
    Posts
    38
    Quote Originally Posted by stahta01 View Post
    I was wondering if he was a very young genius or an AI program.
    "Genius"! Now I've heard everything. You people are crazy.

  10. #10
    Registered User
    Join Date
    Dec 2018
    Posts
    38
    Quote Originally Posted by laserlight View Post
    I think he's just a learner who likes to do a shotgun approach, which I guess works for some people
    Clearly it doesn't work for him since he shows no evidence of understanding or learning anything. You are just encouraging him to be lazy and not read a book like a normal human.

  11. #11
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,352
    Quote Originally Posted by RyanC
    I'm asking if I have a function for instance String(char A[40], int size) , my question are we taking into consideration the given array for calculating the time complexity/space of that function?
    Obviously. Note that this is a plausible call to the String function:
    Code:
    char my_real_array[12345];
    String(my_real_array, 12345);
    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

  12. #12
    Registered User
    Join Date
    May 2009
    Posts
    4,069
    Quote Originally Posted by bruteforce View Post
    "Genius"! Now I've heard everything. You people are crazy.
    Are you 100 percent sure he is not an 7 or 8 year old genius?

    Tim S.
    "...a computer is a stupid machine with the ability to do incredibly smart things, while computer programmers are smart people with the ability to do incredibly stupid things. They are,in short, a perfect match.." Bill Bryson

  13. #13
    Registered User
    Join Date
    May 2016
    Posts
    104
    Quote Originally Posted by stahta01 View Post
    Are you 100 percent sure he is not an 7 or 8 year old genius?

    Tim S.
    Are you serious?
    I doubt a genius would have such poor grammar and ability of expression. He is borderline incoherent at points. Even google translate would generate better posts. He is a troll alright, although not a good one. Admittedly he got me recently, when I replied to one of his threads. But that's only because I have the tendency to focus on the question and ignore the user name, not falling for that again.

    Don't get me wrong, I like trolls -good ones that is. I don't know, there's a certain je ne sais quoi about 'em that I quite enjoy.
    This is one of my all time favorites:
    My (25 M) girlfriend (26 F) baked all the beans, now I consider to end our relations? What does I do? : copypasta

  14. #14
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    38,741
    Quote Originally Posted by stahta01 View Post
    Are you 100 percent sure he is not an 7 or 8 year old genius?

    Tim S.
    4 years of board membership and zero progress in learning anything puts bounds on both assertions.
    Not that young, and not that smart.
    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.

  15. #15
    Registered User
    Join Date
    Dec 2018
    Posts
    38
    Quote Originally Posted by stahta01 View Post
    Are you 100 percent sure he is not an 7 or 8 year old genius?
    I like your AI idea better.
    Or a brain in a vat, sans brain.
    Idiot savant, emphasis on idiot.
    Cat on a keyboard.
    Noise in a cable.
    Indigestion?

    Anyone who insists on interacting with him should be directed to the NULL pointer saga of 2015. That will cure them. It's painfully reminiscent of what's going on now.

    People have been telling this guy to "read a book" for four years.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 1
    Last Post: 03-22-2016, 11:00 AM
  2. Space Complexity of Radix Sort
    By gaurav_13191 in forum C Programming
    Replies: 1
    Last Post: 09-02-2013, 12:09 PM
  3. Filling 2D array complexity.
    By Mr.Lnx in forum C Programming
    Replies: 8
    Last Post: 03-24-2013, 07:08 PM
  4. space complexity of recursive function
    By daniig in forum C Programming
    Replies: 2
    Last Post: 01-23-2013, 12:35 PM
  5. array search complexity problem
    By vnbp8187 in forum C Programming
    Replies: 6
    Last Post: 02-24-2011, 12:45 PM

Tags for this Thread