Is it possible to slice an array in constant time?


#1

is there anyway i can get a subpart of an array in constant time rather than linear time


#2

Getting an individual element counts as getting a part of an array in constant time (yeah, it’s trivial and most likely not what you want)

You can shrink an array by setting its length to a smaller value, but you don’t want to do it if you don’t want to lose data (or if you want to preserve your array).

I’m not sure if it’s possible to get a part of an array in constant time, since getting a part of an array implies copying data, and getting those data means iterating through some part of the original array.

But I’m not really sure though. Maybe the JS engine makes some optimizations. I can’t try it because I’d quickly run out of precious RAM if I tried making a billion-size array (and making a copy of it).


#3

then is it possible to insert an element in constant time in any programming language because i have an algorithm that will sort in O(log(n!)) if it is possible either to slice or insert in constant time
Thank you for your help so far


#4

It depends on the data structure. Data structures with constant time insertion that come to mind are linked lists, hash tables, and hash sets. If by “insertion” you mean “adding an element somewhere in the middle”, then I don’t think you can do that easily in regular arrays (I’m imagining you’ll have to make a new array that’s one element larger then copy the elements to the new one except you save an extra slot to put the element that you want to insert (you can sort of avoid the “make a new array” issue if you implement an array list, but that’s still linear time)).

Can anyone offer some insight?

Can you describe it? I tried graphing log(n!) and it grows slower than n log(n). I’ve read that you can’t make a sorting algorithm with a better time complexity than that.


#5

it is basically that in insertion sort instead of moving the element until you find its position you apply binary search to the sorted part to find the position of the new element


#6
def binary_search(arr,key):
    ll=0
    ul=len(arr)-1
    while(ll<=ul):
        mid=ll+ul//2
        if key<arr[mid] and mid==0:
            return mid
        elif key<arr[mid] and key>arr[mid-1]:
            return mid
        elif key<arr[mid]:
            ul=mid
        else:
            ll=mid
def sort(a):
    i=1
    print(a)
    while i<len(a):
        print(a)
        j=i
        pos=binary_search(a[:j],a[j])
        if pos==0:
            a[:j+1]=[a[j]]+a[:j]
        else:

            a[:j+1]=a[:pos]+[a[j]]+a[pos:j+1]
        i=i+1
    return(a)
print(sort([6,5,4,3,2,1]))

#7

this is the code^^ the runtime will be
log(1) +log(1)…log(n)
=log(n!)
but that will only work if slicing or insertion can be done in constant time