search
Log In
1 vote
225 views

An array of unknown size is filled with special symbols let's say '#'. Time required to find the size of array is

1) O(1)

2) O(logn)

3) O(n)

4) O((logn)2)

in Algorithms 225 views
0
is it 2)  ?
0

I think...

it is O(1)...

0
how ?
0

@Diksha Aswal @ hs_yadav  Approach?

0
I think it would take O(logn)

Traverse it exponentially, i.e traverse with modification in Binary search
0
yes... same approach as Ashwin's
0

let 

S is an array...then...let starting address is 100 and having 5 element of 1 byte...then

&S+1 will return  100+5*1=105....now conside.. S=100

calculate....105-100=   5/size of an element  .....

and for given question this ia character...therefro we will assume size is 1 byte..

0
1 -> 2 -> 4 -> 8 -> 16 ->32 ...... -> 1024

Now, If the last element is 513 (OR 1023 OR 768 whichever is the worst case), then how to proceed?
0
yes, it will take O(logn) time.
0

joshi_nitish how?

0
0
(d) option...?? @srivivek
0
No. Answer given is O(logn)

But I am not getting it
0
apply binary search and move towards right ..you will reach to the end i.e. to 'n' in O(logn) time.
0

Diksha Aswal

1 -> 2 -> 4 -> 8 -> 16 ->32 ...... -> 1024

Now, If the last element(#) is at 513 (OR 1023 OR 768 whichever is the worst case), then how to proceed?

Please log in or register to answer this question.

Answer:

Related questions

0 votes
1 answer
1
0 votes
0 answers
2
0 votes
0 answers
3
93 views
Will the complexity of the function be $\Theta n^{2} or \Theta n^{3}?$
asked Dec 8, 2018 in Algorithms Ajit J 93 views
0 votes
1 answer
4
345 views
Which of the following functions given by their recurrences grows the fastest asymptotically? $T(n) = 8T(n/4) + 100n^2$ $T(n) = 81T(n/9) + 10n^2$ $T(n) = 16T(n/4)+ 100(n \log n)^{1.99}$ $T(n) = 100T(n/100)+ n \log^2 n$
asked Nov 13, 2018 in Algorithms Shubham Aggarwal 345 views
...