R - equivalent function to 'length' with O(log(n)) complexity

Question

I need to write an equivalent function to the function length -without using length, of course. also it must be using a loop.

I need to write two versions for this function. the first, with O(n) complexity, and the second need to be in O(log(n))

EDIT

Also, Suppose that the vector doesn't contain NA values

My Attempt:

my_length_l <- function(x){
  k <- 1
  while(!is.na(x[k])){
  k <- k+1
  }
 return(k-1)
}

for my_length_l:

T(n) = O(n)

second version:

my_length_bs <- function(x){
  if(is.na(x[2])){return(1)}
  else
    {
  k <- 2
  for(i in 1:log2(2^k)){
  while(!is.na(x[k])){
  k <- k+1
  }
  }
    }
 return(k-1)
}

Is my_length_bs indeed exists T(n) = log(n)?

I don't think the logic for checking for NA to determine length is a good idea. Vectors in R can contain missing values. Compare: `x<-c(1, NA, 3, 4, 5); my_length_l(x); length(x)` — MrFlick, Feb 12 '19 at 17:14
yes, your'e correct, but for this case we assume the vector doesn't contain NA values — Noa Even, Feb 12 '19 at 17:16
Your second version doesn't make much sense. You hard-wire in `k = 2` and then have the loop `for(i in 1:log2(2^k)`. Isn't that just `for(i in 1:2)`? — John Coleman, Feb 12 '19 at 17:27
@JohnColeman but the matter is that i need to make the function in O(log(n)) — Noa Even, Feb 12 '19 at 17:35
@Jneven why'd you delete your 5000 digit number question? I was just about to answer... — Gregor Thomas, Jun 13 '19 at 16:04

score 1 · Accepted Answer · answered Feb 12 '19 at 17:38

To answer you immediate question, your second function is just an obfuscated version of your first. The outer for-loop is executed exactly twice and doesn't really do anything, and the inner while loop (which essentially is your first function) does all the work.To see this, put the line print(k) just before k <- k+1 in the inner loop. Then if e.g. you evaluate my_length_bs(1:15) you will see the numbers 2,3,4,...,15 printed in turn. It is still O(n). You need to do a genuine binary search. First go up by powers of 2 until you overshoot the end of the array, and then do a binary search from that starting point to find the actual end of the array.

R - equivalent function to 'length' with O(log(n)) complexity

1 Answers1