[algogeeks] Re: Whats the complexity?
it should involve the exponential increment! somebody plz help On Jul 20, 10:56 pm, Ankur Khurana wrote: > in my opinion , it is log(indexof(k)) > > > > > > On Wed, Jul 20, 2011 at 11:23 PM, Dumanshu wrote: > > that is why m confused. how would u rate this algo? in what order? > > > On Jul 20, 10:44 pm, Ankur Khurana wrote: > > > when n is not defined , you want complexity in terms of ? > > > > On Wed, Jul 20, 2011 at 3:16 PM, Dumanshu wrote: > > > > Given an infinite length list. u got to find index of an element k. > > > > use this approach- > > > > initially, take length as 2^x where x increases from 1 to ... > > > > while (still not found) > > > > { > > > > now if arr[2^x-1] < k, > > > > increment x > > > > else > > > > binarysearch on length 2^(x-1) to 2^(x) > > > > } > > > > > Please help me to find the complexity of this particular approach... > > > > > -- > > > > You received this message because you are subscribed to the Google > > Groups > > > > "Algorithm Geeks" group. > > > > To post to this group, send email to algogeeks@googlegroups.com. > > > > To unsubscribe from this group, send email to > > > > algogeeks+unsubscr...@googlegroups.com. > > > > For more options, visit this group at > > > >http://groups.google.com/group/algogeeks?hl=en. > > > > -- > > > Ankur Khurana > > > Computer Science > > > Netaji Subhas Institute Of Technology > > > Delhi.- Hide quoted text - > > > > - Show quoted text - > > > -- > > You received this message because you are subscribed to the Google Groups > > "Algorithm Geeks" group. > > To post to this group, send email to algogeeks@googlegroups.com. > > To unsubscribe from this group, send email to > > algogeeks+unsubscr...@googlegroups.com. > > For more options, visit this group at > >http://groups.google.com/group/algogeeks?hl=en. > > -- > Ankur Khurana > Computer Science > Netaji Subhas Institute Of Technology > Delhi.- Hide quoted text - > > - Show quoted text - -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Whats the complexity?
in my opinion , it is log(indexof(k)) On Wed, Jul 20, 2011 at 11:23 PM, Dumanshu wrote: > that is why m confused. how would u rate this algo? in what order? > > On Jul 20, 10:44 pm, Ankur Khurana wrote: > > when n is not defined , you want complexity in terms of ? > > > > > > > > > > > > On Wed, Jul 20, 2011 at 3:16 PM, Dumanshu wrote: > > > Given an infinite length list. u got to find index of an element k. > > > use this approach- > > > initially, take length as 2^x where x increases from 1 to ... > > > while (still not found) > > > { > > > now if arr[2^x-1] < k, > > > increment x > > > else > > > binarysearch on length 2^(x-1) to 2^(x) > > > } > > > > > Please help me to find the complexity of this particular approach... > > > > > -- > > > You received this message because you are subscribed to the Google > Groups > > > "Algorithm Geeks" group. > > > To post to this group, send email to algogeeks@googlegroups.com. > > > To unsubscribe from this group, send email to > > > algogeeks+unsubscr...@googlegroups.com. > > > For more options, visit this group at > > >http://groups.google.com/group/algogeeks?hl=en. > > > > -- > > Ankur Khurana > > Computer Science > > Netaji Subhas Institute Of Technology > > Delhi.- Hide quoted text - > > > > - Show quoted text - > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- Ankur Khurana Computer Science Netaji Subhas Institute Of Technology Delhi. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Whats the complexity?
that is why m confused. how would u rate this algo? in what order? On Jul 20, 10:44 pm, Ankur Khurana wrote: > when n is not defined , you want complexity in terms of ? > > > > > > On Wed, Jul 20, 2011 at 3:16 PM, Dumanshu wrote: > > Given an infinite length list. u got to find index of an element k. > > use this approach- > > initially, take length as 2^x where x increases from 1 to ... > > while (still not found) > > { > > now if arr[2^x-1] < k, > > increment x > > else > > binarysearch on length 2^(x-1) to 2^(x) > > } > > > Please help me to find the complexity of this particular approach... > > > -- > > You received this message because you are subscribed to the Google Groups > > "Algorithm Geeks" group. > > To post to this group, send email to algogeeks@googlegroups.com. > > To unsubscribe from this group, send email to > > algogeeks+unsubscr...@googlegroups.com. > > For more options, visit this group at > >http://groups.google.com/group/algogeeks?hl=en. > > -- > Ankur Khurana > Computer Science > Netaji Subhas Institute Of Technology > Delhi.- Hide quoted text - > > - Show quoted text - -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.