Question

Can anyone help with finding complexity of an algorithm ?

Answer 1

Hey thinker, it depends on how complicated the algorithms is.

Could you explain the algorithm please?

Answer 2

I need to find the complexity of binary search technique by considering any 15 numbers.Say we take 1,2,3,...15.
Can you please help out ?

Answer 3

Hey sorry my browser window just closed i have to type everything again.

A couple questions though.
Do you know of recurrences (eg. T(n) = T(n/2) + O(1) ) ?
What a binary tree is?
And how do you need to answer it?

Answer 4

I knw about Binary tress, Binary search trees, how to search elem in that etc...but never tried calculating complexity though..Guess i have seen the formula to calculate running time which u mentioned above..but i still need help in this..
How do i need to answer this : Taking an example of any 15 numbers , i need to calculate the complexity of binary search.Can you post the answer here please.?

Answer 5

The answer is: O(log(n)) (where log is of base 2)

A really easy was to think about it is to picture the array as a binary tree. And the max height of the binary tree is the complexity of binary search. And the height is log(n)

Answer 6

I need the working part of finding the complexity for exactly 15 numbers, i just knew it was O(log n).For example you have 15 numbers , say :
1,2,3,4,5,6,7,8,9,10,11,12,13,14,15 in a BST, and i gotta find say 3 numbers one by one for best case, worst case and avg. case, how do i calculate complexity of finding 8(best case), 16(worst case, 5(avg case) ??

I hope you got what i actually need ..

Answer 7

Just apply the algorithm

8 should be found straight away, because it's in the middle and it's the first element checked

16 should take 4 checks,

5 should also take 4 checks i think

Answer 8

Okay, if i draw the tree this is fine like for eg. complexity to find 16 is 4.(Hope right)

how can i use the formula of complexity in this ? here n=15

Answer 9

The formula is for worst case. For specific elements if you want to know the actual complexity you have to apply the algorithm

Answer 10

can you plz give an example(example to search an elem in the given list) ? I just know that :
best case complexity is O(n)
Avg and worst case is O(log n)
T(n) = T(n/2) + O(1) <---Do i have to substitute n=15 here ?
T(15)=T(8)+1
.
.
????

Answer 11

ok so the list is:

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
n = 15

if we're looking for 15
our search area is from index 0 to index 14 to begin with

[0, 14] middle index: 7 (number 8)

is 15 < 8, no so it should be in the right now the search area is 7 + 1
[8, 14] middle index: 11 (number 12)

is 15 < 12, no so it should be on the right again
[12, 14] middle index: 13 (number 14)

is 15 < 14, again on the right
[14, 14] middle index: 14 (number 15)

and now it's found so depending how you want to count, 4 or 5 checks

Answer 12

So can we say complexity of searching 15(worst case) is 4 ?

Answer 13

yes

Answer 14

alright,thanks a lot for your help ndani, few clarifications/questions in this part though, should i mention the complexity to search 15 as just 4 or O(4) ? Is there a way to work out using any formula ?

Answer 15

There might be for some very specific cases but in general no. O(log(n)) is the worst case. So no matter what you are searching for it will at most take O(log(n)) no longer

Answer 16

okay, so i can use the above method to mention complexities of serching different nodes.
Thank you @ndani14
I guess you can help out when i have more doubts on trees/searching/sorting the next time