0

Hello I have a binary search function and I want to prove that it has Logarithmic complexity.

I have no idea how to prove this and would really use some help

Here are my execution times for the function:

time of execution: 3.1000000000024064e-06
time of execution: 3.099999999998937e-06
time of execution: 4.600000000000437e-06
time of execution: 7.500000000000562e-06
time of execution: 1.559999999999756e-05
time of execution: 1.8299999999998873e-05
time of execution: 3.210000000009039e-05
time of execution: 4.4200000000493844e-05

it is done in order for n=10, n=100 up to n=100000000

I read here that an algorithm is said to run in logarithmic time if its time execution is proportional to the logarithm of the input size.

I understand it but I want to prove it on my example using math and i kinda suck at math :/

If there is no possible way to do this and I am mistaken I would like to at least have some kind of way to show how does my execution time grows depending on the input size.

martineau
  • 119,623
  • 25
  • 170
  • 301
antekkalafior
  • 274
  • 2
  • 16
  • 3
    You cannot prove the complexity of an algorithm by running it and measuring the time it takes. – kaya3 Dec 18 '21 at 19:15
  • Well, that explains it. Actually i am kind of blindly searching for a way to check how does my execution time changes depending on input size – antekkalafior Dec 18 '21 at 19:18
  • 3
    The best way is usually by analysis of the code. If you're studying execution time complexity in a computer science class, they should have already walked you through some examples of this. If you're not taking a class and just learning on your own, do some googling on "how to determine time complexity". This looks like a pretty good primer: https://adrianmejia.com/how-to-find-time-complexity-of-an-algorithm-code-big-o-notation/ – Samwise Dec 18 '21 at 19:21
  • I'll look into that, thank you – antekkalafior Dec 18 '21 at 19:23
  • The basic idea behind most logarithmic algorithms is that in a fixed amount of time you are able to cut the problem in half. So doubling the size of the problem (adding one more bit) is just one more iteration through the loop. For binary search, your search space is low ≤ x ≤ high. By looking at the middle element, you cut the search in half. – Frank Yellin Dec 20 '21 at 02:34

0 Answers0