Waste less time on Facebook — follow Brilliant.
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.

Concept Quizzes

Challenge Quizzes

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 \(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
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)\) time complexity, then the runtime of the code is exactly the same for all possible inputs (intended inputs).



Problem Loading...

Note Loading...

Set Loading...