×
Back to all chapters

# Complexity / Runtime Analysis

A fast algorithm is most useful - you don't want the answer to your question in 10 years, do you? Runtime analysis studies how long an algorithm will take to complete, on average or in the worst case.

# Complexity / Runtime Analysis: Level 2 Challenges

Winston, the pigeon

Back in 2009, citizens of South Africa were frustrated with internet speed. They raced a carrier pigeon against their ISP. The pigeon had a 4 GB USB stick affixed to its leg and was taught to fly to an office, 50 miles away.

The pigeon won by a huge margin -- only 4% of the data was sent through the internet services as the pigeon reached the destination in 2 hours.

You may read the fascinating story, here

As a sidenote, notice that the pigeon would take the same time to carry a data packet of 10 KB to the same destination 50 miles away. But then again, it'd take the same time to carry a 1 TB hard drive, as well.

If $$n$$ is the number of bits being transmitted, how would you characterize the time taken to transmit data by the pigeon (for a reasonable amount of data)?

##### Inspired by Gayle Laakmann McDowell
 1 2 3 4 5 def fun(n): if n==1: return 1 else: return fun(n-1) + fun(n-1) 

What is the time complexity of the above function?

True or false:

If a code has $$O(1)$$ time complexity, then the runtime of the code is exactly the same for all possible inputs (intended inputs).

Notation:

×