Computer Science

# 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:

• $O(\cdot)$ is the Big O Notation.
×