Computer Science

Complexity / Runtime Analysis

Complexity / Runtime Analysis: Level 2 Challenges


Winston, the pigeon 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 nn 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
def fun(n):
    if n==1:
        return 1
        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)O(1) time complexity, then the runtime of the code is exactly the same for all possible inputs (intended inputs).



Problem Loading...

Note Loading...

Set Loading...